A proposition is a statement which has truth value: it is either true (T) or false (F).
Which of the following statements are propositions?
x + y = 6
get a new job!
Mark Twain was a writer
Quentin Tarantino is a famous film-maker
Why sociology is a science?
Sociology is a science
A function is an operation that takes as input one or more parameter values, and produces a single, well-defined output.
A propositional function is a function that produces as output a truth value. It's a statement, then, that becomes a proposition when it is supplied with one or more parameter values.
Propositions may be modified by means of one or more logical operators to form what are called compound propositions.
There are three logical operators:
p: "all squares are rectangles"
q: "all rectangles are squares"
Express the following propositions in natural lanquage.
Are the results True or False?
\(p ∨ q\)
\(p\land q\)
\(¬p\)
p: "Denis likes Sociology"
q: "Denis plays Dota at least 20 hours a week"
Say it in a natural English
\(p ∨ ¬q\)
\(p\land ¬q\)
\(¬(¬q)\)
\(¬p\land ¬q\)
\(¬(p\land q)\)
\((¬p) \land (¬q)\)
Consider the possible values of the compound proposition p ∧ q for various combinations of values of p and q. The only combination of values that makes p ∧ q true is where p and q are both true.
Any other combination will include a false and this will render the whole compound proposition false.
The compound proposition p ∨ q will be true if either p or q (or both) is true.
The only time p ∨ q is false is when both p and q are false.
We summarise conclusions like these in what is called a Truth Table, the truth table for AND being:
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
The truth table for OR is:
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
In the first column (the truth values of p), there are 2 T's followed by 2 F's; in the second (the values of q), the T's and F's change on each row. We shall adopt this order of the rows throughout this text. Adopting a convention for the order of the rows in a Truth Table has two advantages:
The truth table for NOT (¬), since ¬ is a unary operation – one that requires a single proposition as input. So it just two columns – an input and an output – and two rows.
| p | ¬p |
|---|---|
| T | F |
| F | T |
\(Step\hspace{0.1cm} 1:\) Rows
\(Step\hspace{0.1cm} 2:\) Blank Table
\(Step\hspace{0.1cm} 3:\) Input Values
\(Step\hspace{0.1cm} 4:\) Plan your strategy
\(Step\hspace{0.1cm} 5:\) Work down the columns
Construct truth tables and interpret each row
p: Worker is Afro-American
q: Worker has at least 10 years work experience
r: Worker is a female
\(¬p \land ¬q\)
\(q ∨ (p \land ¬q)\)
\(p ∨ (q \land r)\)
\((p ∨ q) ∨ r\)
1 brackets
2 NOT (¬)
3 AND (\(\land\))
4 OR (∨)
Whenever the final columns of the truth tables for two propositions p and q are the same, we say that p and q are logically equivalent, and we write:
p ≡ q
The laws that apply to sets have corresponding laws that apply to propositions also.
\(p \land q ≡ q \land p\)
\(p ∨ q ≡ q ∨ p\)
\((p \land q) \land r ≡ p \land (q \land r)\)
\((p ∨ q) ∨ r ≡ p ∨ (q ∨ r)\)
\(p \land (q ∨ r) ≡ (p \land q) ∨ (p \land r)\)
\(p ∨ (q \land r) ≡ (p ∨ q) \land ( p ∨ r)\)
\(p \land p ≡ p\)
\(p ∨ p ≡ p\)
\(p \land T ≡ p\)
\(p ∨ F ≡ p\)
\(p ∨ T ≡ T\)
\(p \land F ≡ F\)
\(¬(¬p) ≡ p\)
\(¬(p ∨ q) ≡ (¬p) \land (¬q)\)
(sometimes written p NOR q)
\(¬(p \land q) ≡ (¬p) ∨ (¬q)\)
(sometimes written p NAND q)
\(p \land ¬p ≡ F\)
\(p ∨ ¬p ≡ T\)
\(¬T ≡ F\)
\(¬F ≡ T\)
p: "a man has a skateboard"
q: "a man has a bike"
Interprete the result of \(¬p \land ¬q\) in natural language (e. g. "a man has (doesn't have a…) ") if \(p\) and \(q\) are true
For each pair of expressions, construct truth tables to see if the two compaund propositions are logically equivalent (≡):
Build an according proposition with the help of p, q, r, \(\land\), \(∨\), ¬ for further statements, considering that:
p: a man is rooting for "Liverpool"
q: a man is rooting for "Zenit"
r: a man is rooting for "Chicago bulls"
True for a man who is rooting for Chicago bulls and Liverpool but not for Zenit
True for a man who is rooting for Chicago bulls and is not rooting for Liverpool and Zenit
True for a man who is rooting for only one team
