Transcript a+b

Language, Proof and
Logic
The Logic of Boolean
Connectives
Chapter 4
4.1.a
Tautologies and logical truth
A sentence is:
Logically possible if it could be true.
“Bob is funny or Bob is not funny”
“Bob is funny”
“Bob arrived from the Earth to Pluto within 1 min”
Logically necessary (logical truth) if it could not be false.
“Bob is funny or Bob is not funny”
“a=a”
“if c=d and c is a grumber, then d is a grumber”
How about:
“Tet(a)  Cube(a)  Dodec(a)”
“SameRow(a,a)”?
Tautology if every row of its truth table has a “T”.
You try it, page 100
4.1.b
Tautologies and logical truth
Tarski’s world necessities
Logical necessities
Tautologies
4.2
Logical and tautological equivalence
Two sentences S1 and S2 are:
Logically equivalent if it is impossible that
S1 is true while S2 is false, or S1 is false while S2 is true.
Tautologically equivalent if S1 and S2 have identical truth
values in their joint truth table.
Construct such tables for:
(AB) vs. AB
A vs. B
((AB)  C) vs. (AB)  C
a=b  Cube(a) vs. a=b  Cube(b)
4.3
Logical and tautological consequence
A sentence S is a logical consequence of sentences P1,…,Pn if
it is impossible that S is false while each of P1,…,Pn is true.
A sentence S is a tautological consequence of sentences P1,…,Pn if
in every row of the joint truth table, whenever each of P1,…,Pn is
true, so is S.
Is Cube(a) a logical consequence of Cube(b), a=b? Is it also a
tautological consequence?
Is AB a logical consequence of BA? How’bout vice versa?
Is B a logical consequence of AB, A?
4.4
Tautological consequence in Fitch
Ana Con vs. FO Con vs. Taut Con
You try it, p. 117
4.5.a
Pushing negation around
The principle of substitution of logical equivalents:
If P  Q, then S(P)  S(Q).
Negation normal form (NNF): negation is applied only to atoms.
De Morgan’s laws allow us to bring any formula down to NNF:
 ((AB)C)   (AB)C
  (AB)C
 (AB)C
4.5.b
Commutativity, idempotence, associativity
(AB)C((BA)B)  (AB)C((BA)B)
Commutativity:
PQ  QP
PQ  QP
Idempotence:
 (AB)C((BA)B)
 (AB)C(BAB)
 (AB)C(ABB)
 (AB)C(AB)
PP  P
PP  P
 (AB)(AB)C
Associativity:
 (AB)C
P(QR)  (PQ)R  PQR
P(QR)  (PQ)R  PQR
Chain of
equivalences
4.6.a
Conjunctive and disjunctive normal forms
Distribution of  over +: a(b+c) = ab + ac
Hence, e.g., (a+b)(c+d) = (a+b)c + (a+b)d
= ac + bc + (a+b)d
= ac + bc + ad + bd
Disjunctive normal form (DNF):
disjunction of one or more conjunctions of literals
Conjunctive normal form (CNF):
conjunction of one or more disjunctions of literals
What are these?
(ABC)(AD)B
(A(BC))D
(AB)C
AB
4.6.b
Conjunctive and disjunctive normal forms
Distribution of  over : P(QR)  (PQ)(PR)
Allows us to bring any NNF to DNF
Distribution of  over : P(QR)  (PQ)(PR)
Allows us to bring any NNF to CNF
(AB)(CD)  [(AB)C]  [(AB)D]
 (AC)  (BC)  [(AB)D]
 (AC)  (BC)  (AD)  (BD)
(AB)(CD)  [(AB)C]  [(AB)D]
 (AC)  (BC)  [(AB)D]
 (AC)  (BC)  (AD)  (BD)