COMP2022|2922 Models of Computation
Lesson 1: Propositional Logic Presented by
Sasha Rubin
School of Computer Science
Which logics?
1. Propositional logic
A logic for computing with and reasoning about, e.g., statements such as conditionals in programming, digital circuits.
2. Predicate logic
A logic for computing with and reasoning about, e.g., the correctness of programs, knowledge-bases in AI, declarative programs, database queries.
1/38
What makes up a logic?
1. Syntax tells us the structure of expressions, or the rules for putting symbols together to form an expression.
– (1 + (y × 3)) is an arithmetic expression/formula
2. Semantics refers to the meaning of expressions, or how they are evaluated.
– Itevaluatesto13ifweknowthaty=4.
3. Deduction is a syntactic mechanism for deriving new true expressions from existing true expressions.
– Ifweknowthatz=x+ythenwecandeducethatz=y+x.
2/38
Propositional logic
– You can write propositional logic formulas in most programming languages.
– In Python and Java these are called Boolean expressions
– They are usually used as conditions for control flow, e.g., inside an if or a while.
3/38
Warmup
Do the following two Java Boolean expressions say the same thing?
1. !(x >= 5 && x != y) 2. (x < 5 || x == y)
4/38
Warmup
Do the following two Java Boolean expressions say the same thing?
1. !(x >= 5 && x != y) 2. (x < 5 || x == y)
Note
- They are syntactically different (they look different).
- They are semantically equivalent (they mean the same thing).
- In the sense that no matter the values of x, y, they evaluate to the same thing (i.e., either both true or both false).
- If we know one is true we can infer the other is true.
- Use that not(A and B) is equivalent to (not A or not B), no matter what conditions A and B represent.
4/38
Warmup
Do the following two statements say the same thing?
1. There are fires outside Sydney and the air in Sydney is polluted.
2. The air in Sydney is polluted and there are fires outside Sydney.
5/38
Warmup
Do the following two statements say the same thing?
1. There are fires outside Sydney and the air in Sydney is polluted.
2. The air in Sydney is polluted and there are fires outside Sydney.
Note
- We are not asking if the statements are true or not.
- The statements create different images: the first conveys that the fires are causing the pollution, the second that there is already pollution that may be made worse by the fires.
5/38
Warmup
Do the following two statements say the same thing?
1. There are fires outside Sydney and the air in Sydney is polluted.
2. The air in Sydney is polluted and there are fires outside Sydney.
Note
- We are not asking if the statements are true or not.
- The statements create different images: the first conveys that the fires are causing the pollution, the second that there is already pollution that may be made worse by the fires.
- However, logically, the statements are saying the same thing.
- If we know that one is true, we can infer the other is true.
- The reason for this is that we can use a law that says that “F and P” means the same as “P and F”, no matter what F and P represent.
5/38
Warmup
Do the following two statements say the same thing?
1. If the food is good, then the food is not cheap 2. If the food is cheap, then the food is not good
6/38
Warmup
Do the following two statements say the same thing?
1. If the food is good, then the food is not cheap 2. If the food is cheap, then the food is not good
Note
- We are not asking if the statements are true or not.
- The statements create different images: Good but not cheap food conveys that it is expensive, while cheap but not good food conveys that it is rotten.
6/38
Warmup
Do the following two statements say the same thing?
1. If the food is good, then the food is not cheap 2. If the food is cheap, then the food is not good
Note
- We are not asking if the statements are true or not.
- The statements create different images: Good but not cheap food conveys that it is expensive, while cheap but not good food conveys that it is rotten.
- However, logically, the statements are saying the same thing, i.e., that this food is not both good and cheap
- If we know that one is true, we can infer the other is true.
- The reason for this is that “if G then not C” means the same as “if C then not G”, no matter what G and C represent.
6/38
Propositions
Propositional logic is about statements that can be true or false (although we may not know which). Not every statement can be thought of as a proposition.
Which of the following are propositions?
- If this food is good, then this food is not cheap. - Where are we?
-2<5
7/38
Propositions
Propositional logic is about statements that can be true or false (although we may not know which). Not every statement can be thought of as a proposition.
Which of the following are propositions?
Assume that i is an integer variable, and x is a Boolean variable. -i
- i=7
-x
- x=true
- (i < 2 || i > 5) – (i < 2 && x)
7/38
In a nutshell
Logic of propositional formulas
1. Syntax
(p ∧ (q ∨ p)) is a propositional logic formula 2. Semantics
It evaluates to 0 if p = 0, q = 1. 3. Deduction
If we know the condition (p ∧ (q ∨ p)) is true, we can deduce that p is true.
8/38
Syntax tells us the structure of expressions, or the rules for putting symbols together to form an expression.
9/38
Syntax
Java and Python each have their own syntax for writing propositional formulas. We will use another syntax which is the standard in computer science and mathematics.
Name
Prop. Logic Python Java
conjunction disjunction negation implication bi-implication top/verum bottom/falsum atoms formulas
∧ and && ∨ or || ¬ not ! →
↔ ==
==
true
false
Boolean variables Boolean expressions
⊤
⊥
p, q, r, . . . F, G, H, . . .
True
False
Boolean variables Boolean expressions
10/38
Syntax
We now precisely define the syntactic rules for definining formulas of Propositional Logic.
Definition
- A propositional atom (or simply atom1) is a variable of the form p1,p2,p3,... (or alternatively p,q,r,...)
- A propositional formula (or simply formula2) is defined by the following recursive process:
1. Every atom is a formula
2. If F is a formula then ¬F is a formula.
3. If F,G are formulas then (F ∨G) as well as (F ∧G) are
formulas.
1Also called: propositional variable, atomic proposition, atomic formula. 2Also called: Boolean formula.
11/38
Syntax
Example
Which of the following are formulas? 1. ¬p
2. (¬p)
3. ¬¬p
4. ¬p∨q
5. (¬p∨q)
6. ¬(p∨q)
7. (r∧¬(p∨q))
12/38
Syntax
Why do we need this mathematical definition of formula? 1. It is unambiguous.
- If we disagree on whether something is a formula, we just consult the definition
2. It allows one to design algorithms that process formulas using recursion as follows:
- The base case is rule 1 of the definition
- The recursive case are rules 2 and 3 of the definition
3. One can prove things about propositional formulas.
13/38
Syntax
A formula which occurs in another formula is called a subformula.
Exercise
Give a recursive process that defines the set SubForms(G) of all subformulas of G.
14/38
Syntax
Abbreviations
1. (F1 → F2) instead of (¬F1 ∨ F2)
The symbol → is called “implication” (F1 → F2) is read “F1 implies F2”
2. (F1↔F2)insteadof(F1→F2)∧(F2→F1) The symbol ↔ is called “bi-implication” (F1 ↔F2) is read “F1 if and only if F2”
3. ⊥insteadof(F∧¬F)
The symbol ⊥ is called “bottom” or “falsum”
4. ⊤insteadof(F∨¬F)
The symbol ⊤ is called “top” or “verum”.
5. (ni=1Fi)insteadof(...((F1∨F2)∨F3)···∨Fn) 6. (ni=1Fi)insteadof(...((F1∧F2)∧F3)···∧Fn)
15/38
Homework
Example
Consider the formula ¬((p ∧ q) ∨ ¬r).
- How do you apply the rules to build this formula? Give the
sequence of rules you use to build the following formula. - This formulas has 7 subformulas. What are they?
16/38
Semantics refers to the meaning of expressions, or how they are evaluated
17/38
Semantics of Propostional Logic = Assignments + Truth-values of Formulas
18/38
Semantics: truth values
Recall: Semantics refers to how you derive the value of a formula based on the values of its atomic subformulas.
- The elements of the set {0, 1} are called truth values
- We read 1 as “true”, and 0 as “false”
- After we assign truth values to atoms . . . (e.g., p = 0, q = 1)
- we can compute the truth values of formulas. (e.g., the truth value of (p ∨ q) is 1).
19/38
Semantics: truth values
Recall: Semantics refers to how you derive the value of a formula based on the values of its atomic subformulas.
- The elements of the set {0, 1} are called truth values
- We read 1 as “true”, and 0 as “false”
- After we assign truth values to atoms . . . (e.g., p = 0, q = 1)
- we can compute the truth values of formulas. (e.g., the truth value of (p ∨ q) is 1).
Here are the rules for doing this computation . . .
19/38
Semantics: truth tables
The formula ¬F is true if and only if the formula F is false.
F ¬F 01 10
20/38
Semantics: truth tables
The formula (F ∧ G) is true if and only if both the formulas F and G are true.
F G (F∧G) 000 010 100 111
20/38
Semantics: truth tables
The formula (F ∨G) is true if and only if either F or G or both are true.
F G (F∨G) 000 011 101 111
20/38
Semantics
Example
Evaluate the formula F = ¬((p ∧ q) ∨ r) under the assignment p = 1, q = 1, r = 0.
p q r ¬((p∧q)∨r) 110
21/38
Semantics
Evaluate the formula F = ¬((p ∧ q) ∨ r) under all assignments of the atoms p, q, r.
p q r ¬((p∧q)∨r) 000
001
010
011 100 101 110 111
22/38
Semantics
We now formalise these truth tables with the following definition of the semantics.
Definition
- An assignment is a function α assigning truth values to atoms. So α(p) is the truth value of p under assignment α.
- The truth value tv(F, α) of a formula F under the assignment α is given by the following recursive procedure:
1. The truth value of an atom p is just α(p).
2. The truth value of a formula of the form ¬F is 1 if the truth
value of F is 0, and 0 otherwise.
3. The truth value of a formula of the form (F ∧G) is 1 if the
truth values of both F and G are 1, and 0 otherwise.
4. The truth value of a formula of the form (F ∨G) is 1 if the
truth values of either F or G or both are 1, and 0 otherwise.
23/38
Semantics
We now formalise these truth tables with the following definition of the semantics.
Definition
- An assignment is a function α assigning truth values to atoms. So α(p) is the truth value of p under assignment α.
- The truth value tv(F, α) of a formula F under the assignment α is given by the following recursive procedure:
1. tv(p, α) = α(p) for every atom p
2. tv(¬F,α) = 3. tv((F∧G),α)= 4. tv((F∨G),α)=
0 1
1 0
1 0
if tv(F,α) = 1 if tv(F,α) = 0
if tv(F,α) = 1 and tv(G,α) = 1 otherwise
if tv(F,α) = 1 or tv(G,α) = 1 otherwise
23/38
Semantics
Example
Suppose α(p1) = 1 and α(p2) = 0. Compute the truth value of (¬p1 ∨ p2) under α.
24/38
Semantics
Why do we need this precise definition of semantics?
1. It is unambiguous.
- If we disagree on the truth value of F under α, we just consult the definition.
2. This definition is implemented by the runtime environment of Python and Java to compute the values of Boolean expressions.
3. One can prove things about formulas.
25/38
Semantics
Terminology
- In case the truth value of F under α is equal to 1, we say that α makes F true or that α satisfies F .
- The standard notation in logic for this is different: we say that α models F, written: α |= F.
The symbol |= is called the “double-turnstile”.
- A formula F is satisfiable if at least one assignment satisfies F. Otherwise F is unsatisfiable.
26/38
Exercise
Convince yourself that here is an equivalent (and more succinct) way to define the truth value of formulas under an assignment α:
1. tv(p, α) = α(p) for atoms p
2. tv(¬F,α)=1−tv(F,α).
3. tv((F ∧ G), α) = min{tv(F, α), tv(G, α)}. 4. tv((F ∨ G), α) = max{tv(F, α), tv(G, α)}.
27/38
Semantics
Example
Suppose α(p1) = 1 and α(p2) = 0. Compute the truth value of (¬p1 ∨ p2) under α.
tv((¬p1 ∨ p2), α) = max{tv(¬p1, α), tv(p2, α)} = max{1 − tv(p1, α), tv(p2, α)}
= max{1 − α(p1), α(p2)} = max{1 − 1, 0} = 0
Rule 4. Rule 2. Rule 1.
28/38
Semantics: implication
F G (F→G) 001 011 100 111
29/38
Semantics: implication
- We now discuss why (F →G) is defined as (¬F ∨ G).
- When is the formula (F → G) true?
- It is true whenever, if F is true, then
also G is true.
- So, if F is not true, then it doesn’t matter whether G is true or not, the formula (F → G) will still be true.
- Note. Implication is not the same as the programming construct
“If condition is true then do instruction”. And it does not mean that F causes G to be true.
F G (F→G) 001 011 100 111
30/38
Semantics: implication
Let’s write a function that returns whether or not you are ready to go outside. The constraint is that if it is raining, then, to be ready, you should be carrying_umbrella.
1 def ready:
2 return (not raining or carrying_umbrella)
If Python had a symbol for implication, say →, then we could have written:
1 def ready:
2 return (raining → carrying_umbrella)
31/38
Connection with natural language
What is the connection between propositional logic and natural language? Although logic can be used to model propositions of natural language, there are important differences.
- In logic, semantics is determined by the assignment and the syntactic structure of the formula.
- In natural language, the semantics also depends on the context.
32/38
Connection with natural language
Disjunction
- Inclusive or: (F ∨ G)
- Exclusive or: ((F ∨ G) ∧ ¬(F ∧ G))
33/38
Connection with natural language
Disjunction
- Inclusive or: (F ∨ G)
- Exclusive or: ((F ∨ G) ∧ ¬(F ∧ G))
Examples
One can reach the airport by taxi or bus
You can choose to save your money or your life The error is in the program or the sensor data The program or the sensor data are erroneous
Inclusive Exclusive Exclusive? Inclusive?
33/38
Connection with natural language
Implication/equivalence
“Eating fast-food is equivalent to aiding the destruction of the world’s rainforests”
- This looks like an equivalence,
- but is more likely an implication (it’s unlikely that the speaker is claiming that destroying rainforests results in eating fast food).
34/38
For you think about
How does the following important idea apply to syntax and semantics of propositional logic?
In Computer Science we start with the simplest possible systems, and sets of rules that we haven’t necessarily confirmed by experiment, but which we just suppose are true, and then ask what sort of complex systems we can and cannot build. . . it is a mathematical set of tools, or body of ideas, for understanding just about any system—brain, universe, living organism, or, yes, computer.
Scott Aaronson — theoretical computer scientist
35/38
References
- Chapter 1 of Schöning covers syntax and semantics of propositional logic
- We use slightly more readable notation:
- We use p,q,r,... for atoms instead of A,B,C,...
- We use α for assignments instead of A
- We use tv(−) for truth values of a formula instead of A
36/38
Coda: algorithmic issue
Input: A propositional formula F
Output: Yes if F is satisfiable, and No otherwise
- Can one check every assignment? There are infinitely many.
- Fact. Assignments that agree on the atoms occuring in F also
agree on F.
- So we only need to check finitely many assignments.
- If F contains atoms p1, · · · , pn, there are exactly 2n different assignments. Why?
- Test all of them using truth-tables.
37/38
Coda: algorithmic issue
Question. How efficient is this test for satisfiability?
- Suppose F has n atoms.
- Then the truth-table as 2n rows — exponential growth.
- Suppose you can generate a table at the rate of one row per second.
- If n = 80, you will need 280 seconds to write out the table.
- This is about 2.8 million times the age of the universe. Question. Is there a substantially faster method?
- Probably not.
- This is related to the P vs NP problem. See COMP3027:Algorithm Design.
38/38