Logic 2: syntax trees and truth tables Flashcards
Create a syntax tree for the following formula:
((p ↔ q) → r))
. →
/ \
↔ r
/ \
p q
what is parsing?
Analysing the structure of any valid formula.
What does a syntax tree do?
It can represent the result of parsing a formula.
What is the highest level connective in the following formula, and why?
((p ↔ q) → r)
→ is the highest level connective. This is because the whole formula is formed from (p ↔ q) and r, by means of this connective.
Create a syntax tree for the following formula:
(p ↔ (q → r))
. ↔
/ \
p →
/ \
q r
What is the highest level connective in the following formula, and why?
(p ↔ (q → r))
↔ is the highest level connective. This is because the whole formula is formed from (q → r) and p, by means of this connective.
Paraphrase the following formula in English (give an informal interpretation):
((p ∧ q) → r) ∨ (p → (¬r))
if p and q are both true, then r is true, or, if p is true then r is false.
How can we give a formal meaning to a formula?
By means of a truth table.
What is the use of a Truth Table?
To give a formal meaning to a formula.
How do we represent ‘is true’ and ‘is false’ in a truth table?
T, F
T
What is the difference between true and T in the above table?
true is a syntactic object (like the keyword while in a programming language), whereas T stands for the property of being true.
A ¬A
T F
F T
What does the above truth table tell us?
The truth table tells us all we need to know about the meaning of the connective ¬:
if a proposition is true, then its negation is false, and vice versa.
The conjunction A ∧ B of A and B is true precisely when A and B are both
true. Express this formally in a truth table…
A B A ∧ B
T T T
T F F
F T F
F F F
Create a truth table for the following formula:
A ∧ B
A B A ∧ B
T T T
T F F
F T F
F F F
The disjunction A ∨ B is true precisely when either one of A and B is true, or
both are true. Express this formally in a truth table…
A B A ∨ B
T T T
T F T
F T T
F F F
Create a truth table for the following formula:
A ∨ B
A B A ∨ B
T T T
T F T
F T T
F F F
we define A → B to be false
when A is true and B is false, and to be true in all other cases. Express this formally in a truth table…
A B A → B
T T T
T F F
F T T
F F T
Create a truth table for the following formula:
A → B
A B A → B
T T T
T F F
F T T
F F T
A ↔ B is true when A
and B have the same truth values.
Express this formally in a truth table…
A B A ↔ B
T T T
T F F
F T F
F F T
Create a truth table for the following formula:
A ↔ B
A B A ↔ B
T T T
T F F
F T F
F F T
What is the formal term used to describe the assignment of truth values to all propositional variables occurring in a formula.
interpretation of the formula.
What does the formal term ‘interpret a formula’ mean?
It is a term used to describe the assignment of truth values to all propositional variables occurring in a formula. (AKA creating a truth table)
How does one formally interpret a formula?
By creating a truth table, in which one assigns truth values to all propositional variables occuring in a formula.
Create a truth table for the following formula:
¬(p ∧ q)
p q p ∧ q ¬(p ∧ q)
T T T F
T F F T
F T F T
F F F T
