V Goranko
Revision on propositional logic:
Propositions. Logical Connectives.
Truth values and truth tables.
Propositional formulae. Tautologies.
Logical equivalence.
Logical consequence.
Logical correctness of propositional arguments.
Valentin Goranko DTU Informatics
August 2010
V Goranko
Propositions and propositional logical connectives
Proposition: statement which can be assigned a (unique)truth value: true or false.
Propositional logical connectives:
• negation: not, denoted by ¬;
• conjunction: and, denoted by∧ (or, sometimes by &);
• disjunction: or, denoted by ∨;
• implication: if . . . then . . ., denoted by→;
• biconditional: . . . if and only if . . ., denoted by↔.
Examples of composite propositions:
• “It is notthe case that two plus two equals five.”
• “Two plus two equals five and/or the sun is hot.”
• “Iftwo plus two equals five then the sun is hot.”
• “Two plus two equals five if and only if the sun is hot.”
“Mary isnotclever or,ifMary likes logic then Mary is clever andMary is notlazy.”
V Goranko
The propositional connectives as truth value functions
Each propositional connective acts on the truth values of the component propositions in a precise way:
• ¬A is trueif and only ifA is false.
• A∧B is trueif and only if both AandB are true.
• A∨B is trueif and only if either ofA or B (possibly both) is true.
• A→B is true if and only if A is false orB is true, i.e. if the truth of Aimplies the truth of B.
• A↔B is true if and only ifA andB have the same truth-values.
V Goranko
Truth tables
These rules can be summarized in the followingtruth tables, where Tstands for ‘true’ and stands for ’false’:
p ¬p T F F T
p q p∧q p∨q p →q p ↔q
T T T T T T
T F F T F F
F T F T T F
F F F F T T
V Goranko
Computing the truth value of a proposition
Suppose that
“Mary is clever.”: T;
“Mary is lazy.”: F;
“Mary likes logic.”: T
To compute the truth value of the composite proposition:
“Mary is notcleveror,if Mary likes logicthen Mary is cleverand Mary isnotlazy.”
we first write it in asymbolic form, by introducing symbolic names for the atomic propositions occurring in it:
A: “Mary is clever.”
B: “Mary is lazy.”
C: “Mary likes logic.”
V Goranko
Then, the proposition can be written symbolically as:
(¬A)∨(C →(A∧ ¬B)).
Now, we compute its truth value step by step, applying the truth-tables of the respective logical connectives:
(¬T)∨(T→(T∧ ¬F))
=F∨(T→(T∧T))
=F∨(T→T)
=F∨T
=T.
V Goranko
Propositional formulae
Propositional constants: >which represents a true proposition, and⊥which represents a false proposition.
Propositional variables: variables that range over propositions.
Usually denoted byp,q,r, possibly with indices.
Inductive definition ofpropositional formulae:
1. Every propositional constant and every propositional variable is a propositional formula.
2. IfA is a propositional formula then¬Ais a propositional formula.
3. IfA,B are propositional formulae then (A∨B), (A∧B) , (A→B), (A↔B) are propositional formulae.
Examples:
>,¬>,p,¬p,¬¬p,(p∨ ¬q),(p1∧ ¬(p2 → ¬p1)) Outermost pairs of parentheses will often be omitted.
V Goranko
Construction trees, subformulae, main connectives
Construction tree: a tree with nodes labelled with propositional constants, variables, and propositional connectives, such that:
1. Every leaf is labelled by a propositional constant or variable.
2. Propositional constants and variables label only leaves.
3. Every node labelled with ¬has exactly one successor node.
4. Every node labelled with any of ∧,∨,→,↔has exactly two successor nodes - leftandright successor.
Every construction tree defines a formulaC, built starting from the leaves and going towards the root, by applying at every node the formula construction rule corresponding to the label at that node.
The formulae constructed in the process are thesubformulae ofC. The propositional connective labelling the root of the construction tree of a formulaC is the main connectiveof C.
V Goranko
Truth tables of propositional formulae
Example:
(p∨ ¬(q∧ ¬r))→ ¬¬r
p q r ¬r ¬¬r q∧ ¬r ¬(q∧ ¬r) p∨ ¬(q∧ ¬r) (p∨ ¬(q∧ ¬r))→ ¬¬r
T T T F T F T T T
T T F T F T F T F
T F T F T F T T T
T F F T F F T T F
F T T F T F T T T
F T F T F T F F T
F F T
F F F
V Goranko
Simplified truth tables
p q r (p ∨ ¬ (q ∧ ¬ r)) → ¬ ¬ r T T T T T T T F F T T T F T T T F T T F T T T F F F T F T F T T T T F F F T T T F T T F F T T T F F T F F F T F F T T F T T T F F T T T F T F T F F F F T T T F T F T F F F T
F F F
V Goranko
Tautologies
Tautology(or, propositionally valid formula): a formula that obtains truth valueTfor every assignment of truth values to the occurring variables. Notation: |=A.
Examples:
|=p∨ ¬p,
|=¬(p∧ ¬p),
|= ((p∧(p →q))→q)
Testing tautologies with truth-tables:
p q p →q p∧(p →q) (p∧(p →q))→q
T T T T T
T F F F T
F T T F T
F F T F T
V Goranko
Contradictions, satisfiable formulae
Contradictionis a formula that always takes truth valueF.
Examples: p∧ ¬p,¬((p∧q)→p)
Thus, the negation of a tautology is a contradiction and the negation of a contradiction is a tautology.
A formula issatisfiableif it is not a contradiction.
Example: p,p∧ ¬q, etc.
V Goranko
Logical equivalence of propositional formulae
Propositional formulaeAand B are logically equivalent, denoted A≡B, if they obtain the same truth value under any truth valuation (of the variables occurring in them). Examples:
¬(p∧q) ≡ ¬p∨ ¬q
p q ¬ (p ∧ q) ¬ p ∨ ¬ q T T F T T T F T F F T T F T T F F F T T T F F T T F F T T F T F T F F T F F F T F T T F
p∧(p∨q) ≡ p∧p ≡ p p q p ∧ (p ∨ q) p ∧ p T T T T T T T T T T T F T T T T F T T T F T F F F T T F F F F F F F F F F F F F
V Goranko
Some basic properties of logical equivalence
IA≡B iff|=A↔B.
I≡is anequivalence relation.
IMoreover,≡is a congruence with respect to the propositional connectives, i.e.:
B if A≡B then ¬A≡ ¬B, and
B if A1 ≡B1 andA2 ≡B2 then (A1•A2)≡(B1•B2), where• ∈ {∧,∨,→,↔}.
Theorem for equivalent replacement:
LetA,B,C be any propositional formulaep be a propositional variable. IfA≡B thenC(A/p)≡C(B/p).
V Goranko
Some important logical equivalences
• Idempotency:
p∧p ≡p; p∨p≡p.
• Commutativity:
p∧q≡q∧p; p∨q≡q∨p.
• Associativity:
(p∧(q∧r))≡((p∧q)∧r); (p∨(q∨r))≡((p∨q)∨r).
Note that this property allows us to omit the parentheses in multiple conjunctions and disjunctions.
• Absorption:
p∧(p∨q)≡p; p∨(p∧q)≡p.
• Distributivity:
p∧(q∨r)≡(p∧q)∨(p∧r);
p∨(q∧r)≡(p∨q)∧(p∨r).
V Goranko
Other useful logical equivalences
• A∨ ¬A≡ >; A∧ ¬A≡ ⊥;
• A∧ > ≡A; A∧ ⊥ ≡ ⊥;
• A∨ > ≡ >; A∨ ⊥ ≡A.
• A→B≡ ¬A∨B.
• A↔B≡(A→B)∧(B→A).
• A→B≡ ¬B→ ¬A.
V Goranko
Propositional logical consequence
A propositional formulaC is a logical consequence from the propositional formulaeA1, . . . ,An, denoted
A1, . . . ,An|=C, ifC is true whenever all A1, . . . ,An are true,
i.e., every assignment of truth-values to the variables occurring in A1, . . . ,An,C which renders the formulae A1, . . . ,An true, renders the formulaC true, too.
IfA1, . . . ,An|=C, we also say that C follows logicallyfrom A1, . . . ,An, and that A1, . . . ,An logically imply C.
Logical consequence is reducible to validity:
A1, . . . ,An|=C iff A1∧. . .∧An|=C iff |= (A1∧. . .∧An)→C.
V Goranko
Testing propositional consequence with truth tables
Ip,p →q|=q
p q p p →q q
T T T T T
T F T F F
F T F T T
F F F T F
Ip→r,q →r |= (p∨q)→r
p q r p →r q →r p∨q (p∨q)→r
T T T T T T T
T T F F F T F
T F T T T T T
T F F F T T F
F T T T T T T
F T F T F T F
F F T T T F T
F F F T T F T
V Goranko
Valid rules of propositional inference
Arule of propositional inference(for short,inference rule) is a scheme:
P1, . . . ,Pn
C ,
whereP1, . . . ,Pn,C are propositional formulae. The formulae P1, . . . ,Pn are called premisesof the inference rule, andC is its conclusion.
An inference rule isvalidif its conclusion logically follows from the premises.
Apropositional inference is an instance of a rule, where
propositions are uniformly replaced by the propositional variables.
A propositional inference islogically correct(or, valid) if it is an instance of a valid inference rule.
V Goranko
Propositional inference: examples
IConsider the propositional inference:
Mary is singing.
If Mary is singing, then Mary is happy.
Mary is happy.
It is obtained from the following rule, called Modus Ponens:
p, p →q q
This rule is valid, therefore, the inference is logically correct.
INow consider the propositional inference:
2 plus 2 equals 4.
If 5 is greater than 3, then 2 plus 2 equals 4.
5 is greater than 3.
It is based on the rule
p, q →p q
which is not valid. Therefore, the inference is not logically correct.
