Introduction to Discrete Mathematics

Proposition Logic

Notes By Pr. El Hadiq Zouhair

1 / 13

Overview

Proposition logic is a branch of logic studying ways of modifying and joining propositions.
Propositions are crucial in mathematics, as all proofs rely on propositional logic.
It was first seriously studied by Aristotle, who was also the first to popularize most topics covered in this section.
You will learn about propositions and logical operators in this lesson.

2 / 13

Proposition

A proposition is a mathematical statement that is either true or false:

This course is on discrete mathematics.
3 is greater than 4.

Interrogative, exclamatory and imperative sentences are not propositions:

Why are some sheep black?
Do the dishes.

SymPy — imports (run once) from sympy import symbols, Not, And, Or, Implies, Equivalent, simplify from sympy.logic.boolalg import truth_table, to_cnf, to_dnf from sympy.logic.inference import satisfiable p, q = symbols('p q')

SymPy [int(True), int(False)] # [1, 0]

3 / 13

Basic Operators

Let $p$ and $q$ be propositions.

The negation of $p$ ($\neg$, !, Not) is the opposite of $p$; states "$p$ is false":

SymPy Not(p) # or ~p

$p$	$\neg p$
True	False
False	True

The conjunction of $p$ and $q$ ($\wedge$, &&, And) is "$p$ and $q$":

SymPy And(p, q) # or p & q

4 / 13

Basic Operators (continued)

The disjunction of $p$ and $q$ ($\vee$, ||, Or) is "$p$ or $q$":

SymPy Or(p, q) # or p | q

$p$	$q$	$p \vee q$
True	True	True
True	False	True
False	True	True
False	False	False

SymPy — generate truth table for row in truth_table(Or(p, q), [p, q]): print(row) # prints (vals, result) tuples

5 / 13

Example

Let $p$ = "I studied for the exam" and $q$ = "I passed the exam."

Express in English:

$\neg q$ — I did not pass the exam.
$p \wedge q$ — I studied for the exam and I passed the exam.

Express in logic:

I did not pass the exam, nor did I study for it. $\neg q \wedge \neg p$
I studied for the exam, but I did not pass it. $p \wedge \neg q$

SymPy — verify Not(q) # ¬q And(p, q) # p ∧ q And(Not(q), Not(p)) # ¬q ∧ ¬p And(p, Not(q)) # p ∧ ¬q

6 / 13

More Operators

The conditional $p \Rightarrow q$ ($\Rightarrow$, Implies) is "If $p$, then $q$":

SymPy Implies(p, q)

$p$	$q$	$p \Rightarrow q$
True	True	True
True	False	False
False	True	True
False	False	True

The biconditional $p \Leftrightarrow q$ ($\Leftrightarrow$, Equivalent, iff) is "$p$ if and only if $q$":

SymPy Equivalent(p, q)

7 / 13

Example

Let $p$ = "It is raining" and $q$ = "Kala wants to play outside."

Express in English:

$p \Rightarrow q$ — If it is raining, then Kala wants to play outside.
$\neg q \Leftrightarrow p$ — Kala does not want to play outside iff it is raining.

Express in logic:

Either Kala wants to play outside or it is raining. $q \vee p$
Kala wants to play outside regardless of rain. $(p \Rightarrow q) \wedge (\neg p \Rightarrow q)$

SymPy — simplification expr = And(Implies(p, q), Implies(Not(p), q)) simplify(expr) # simplifies to just: q

8 / 13

Precedence

The precedence of logical operators is as follows:

$() \;>\; \neg \;>\; \wedge \;>\; \vee \;>\; \Rightarrow \;>\; \Leftrightarrow$

P N A O I B Parentheses > Not > And > Or > Implies > Biconditional

Evaluate the following if $p$ = True and $q$ = False:

SymPy p_v, q_v = True, False e = Implies(~p | q, p & ~q) e.subs({p: p_v, q: q_v}) # True

SymPy f = Implies(~p|q|(p&q)|True, p&q) f.subs({p: p_v, q: q_v}) # False

9 / 13

Converse, Contrapositive, Inverse or Opposite?

Consider the conditional proposition $p \Rightarrow q$.

The converse is $q \Rightarrow p$.
The contrapositive is $\neg q \Rightarrow \neg p$.
The inverse is $\neg p \Rightarrow \neg q$.
The opposite is $\neg(p \Rightarrow q)$.

The contrapositive will be useful in future lessons.

SymPy converse = Implies(q, p) contra = Implies(~q, ~p) inverse = Implies(~p, ~q) opposite = Not(Implies(p, q)) # Contrapositive ≡ original: Equivalent(Implies(p,q), Implies(~q,~p)) # True

10 / 13

Logic Gates

A logic gate is a simple switching circuit with an output corresponding to logical operators.

Logic gates are usually represented in a diagram, with the following symbols:

NOT gate	AND gate	OR gate
$p \longrightarrow$ $\neg$ $\longrightarrow \neg p$	$p,q \longrightarrow$ $\wedge$ $\longrightarrow p \wedge q$	$p,q \longrightarrow$ $\vee$ $\longrightarrow p \vee q$

SymPy — gate truth tables for row in truth_table(Not(p), [p]): print(row) # NOT for row in truth_table(And(p,q), [p,q]): print(row) # AND for row in truth_table(Or(p,q), [p,q]): print(row) # OR

They are essential in understanding computing from the ground up.

11 / 13

Summary

A proposition is a mathematical statement that is either true or false, but never both.
The three main logical operators are negation ($\neg$), conjunction ($\wedge$), and disjunction ($\vee$).
Many other operators exist, most importantly the conditional ($\Rightarrow$) and biconditional ($\Leftrightarrow$).
Logical expressions easily get convoluted.

SymPy — key imports for this lesson from sympy import symbols, Not, And, Or, Implies, Equivalent, simplify from sympy.logic.boolalg import truth_table, to_cnf, to_dnf from sympy.logic.inference import satisfiable p, q = symbols('p q')

12 / 13

SymPy Quick Reference

Operation	SymPy function	SymPy operator
Negation	`Not(p)`	`~p`
Conjunction	`And(p,q)`	`p & q`
Disjunction	`Or(p,q)`	`p \| q`
Conditional	`Implies(p,q)`	—
Biconditional	`Equivalent(p,q)`	—
Boole / int	`int(expr)`	—
Truth table	`truth_table(expr,[vars])`	—
Simplify	`simplify(expr)`	—
Satisfiable	`satisfiable(expr)`	—

13 / 13