Logic

Logic Symbols

Symbol	Meaning
$\exists$	There exists
$\forall$	For all
$p\to q$	p implies q (if p, then q)
$p\leftrightarrow q$	p if and only if q This is a connective, like $\wedge$
$p\iff q$	p if and only if q (p and q are equivalent) (This is the same as $\leftrightarrow$ ?)
$p\equiv q$	p is equivalent to q (equal, but for logic) This is a “fact”, like $\in$
$x\in A$	x is an element of A
$A\subseteq B$	A is a subset of B
$A-B$	Difference between set A and B
~p	NOT p (Negation)
$p\wedge q$	$p$ AND $q$
$p\vee q$	$p$ OR $q$
$A_0:=A$	Set $A_0$ to be a working copy of $A$ (not a logic symbol)

Logic Laws

Commutative

• $p\wedge q\equiv q\wedge p$
• $p\vee q\equiv q\vee p$

Associative

• $p\wedge q\wedge r\equiv (p\wedge q)\wedge r\equiv p\wedge (q\wedge r)$
• $p\vee q\vee r\equiv (p\vee q)\vee r\equiv p\vee (q\vee r)$

Distributive

• $p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$
• $p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$
• applying twice: $(p\wedge q)\vee (r\wedge s)\equiv (p\vee r)\wedge (p\vee s)\wedge (q\vee r)\wedge (q\vee s)$ and vice versa

Identities

• $p\wedge true\equiv p$
• $p\vee false\equiv p$

Universal Bound

• $p\vee true\equiv true$
• $p\wedge false\equiv false$

Negation

• $p\vee \sim p\equiv true$
• $p\wedge \sim p\equiv false$

Double Negative

• $\sim (\sim p)\equiv p$

Idempotent

• $p\wedge p\equiv p$
• $p\vee p\equiv p$

Absorption

• $p\vee (p\wedge q)\equiv p$
• $p\wedge (p\vee q)\equiv p$

Implication

• $p\to q\equiv \sim p\vee q$
• $\sim (p\to q)\equiv p\wedge \sim q$ (Can be deduced from the point above)
• no name for this: $p\leftrightarrow q\equiv (\sim p\wedge \sim q)\vee (p\wedge q)$ this is derived from implication law, distributive law, negation law and identity law

De Morgan’s

These laws can be extended to more than two variables

• $\sim (p\wedge q)\equiv \sim p\vee \sim q$

• $\sim (p\vee q)\equiv \sim p\wedge \sim q$

Logical Arguments

Definition

An argument (argument form) is a sequence of statements (statement forms). All statements in an argument, except for the final one are called premises (or assumptions or hypothesis). The final statement is called the conclusion The symbol, $\bullet$, which is read “therefore”, is normally placed before the conclusion.

Example Argument

$p\to q\vee \sim r\text{ (premise)}$ $q\to p\wedge r\text{ (premise)}$ $\bullet p\to r\text{ (conclusion)}$ Note: this argument is invalid

Valid or Invalid

To say that an argument is valid means that no matter what statements are substituted for the statement variables in its premises, if the resulting premises are all true, then the conclusion is also true. i.e. For an argument to be valid: IF all premises are true, THEN conclusion must be true

Test Validity with Truth Table

1. Identify all the premises and conclusion of the argument form
2. Construct a truth table showing the truth values of all the premises and the conclusion
3. Identify critical rows: Rows in which all the premises are true
4. There is a critical row in which the conclusion is false $\to$ The argument form is valid
5. The conclusion in every critical row is true $\to$ The argument form is valid

Syllogism

An argument form consisting of two premises and a conclusion

Modus Ponens

This is a commonly used form of syllogism: if $p$ then $q$ $p$ $\bullet q$

Modus Tollens

Also a commonly used form of syllogism: if $p$ then $q$ $\sim q$ $\bullet \sim p$

Rules of Inference

Rules of Inference are Logical Arguments that are valid. Rules of Inference can be chained together to prove more complex logical arguments.

Modus Ponens

if $p$ then $q$ $p$ $\bullet q$

Modus Tollens

if $p$ then $q$ $\sim q$ $\bullet \sim p$

Generalisation

$p$ $\bullet p\vee q$

The conclusion is a more general form of the premise: Anton is a junior $\bullet$ (More generally,) Anton is a junior or Anton is a senior

Specialisation

$p\wedge q$ $\bullet p$

Discard extraneous information to concentrate on the property of interest Ana knows graph algorithms and Ana knows numerical analysis $\bullet$ (In particular,) Ana knows graph algorithms

Elimination

$p\vee q$ $\sim q$ $\bullet p$

When there are two possibilities and one can be ruled out, the other must be the case

Transitivity

$p\to q$ $q\to r$ $\bullet p\to r$

Proof by Division into Cases

$p\vee q$ $p\to r$ $q\to r$ $\bullet r$

Suppose one thing or another is true If in both cases, a certain conclusion follows, this conclusion must also be true

Contradiction

$\sim p\to false$ $\bullet p$

Conjunction Premises

$p$ $q$ $\bullet p\wedge q$

Conditional (if)

Statements of the form $p\to q$ $p$ is called the hypothesis or antecedent $q$ is called the conclusion or consequent “if $p$, then $q$” ”$p$ only if $q$” ”$p$ is a sufficient condition for $q$” ”$q$ is a necessary condition for $p$“

Vacuously True

In the case that $p$ is false, $p\to q$ is true (vacuously true or true by default)

Implication Law

$p\to q\equiv \sim p\vee q$ $\sim (p\to q)\equiv p\wedge \sim q$ (Can be deduced from above)

Variants of Conditional Statements

Contrapositive

The contrapositive of $p\to q$ is $\sim q\to \sim p$ The contrapositive of “if p then q” is “if ~q then ~p” A conditional statement is always logically equivalent to its contrapositive $p\to q\equiv \sim q\to \sim p$ e.g. If Howard can swim across the lake, then Howard can swim to the island $\equiv$ If Howard cannot swim to the island, then Howard cannot swim across the lake

Converse

The converse of $p\to q$ is $q\to p$ The converse of “if p then q” is “if q then p” $p\to q\not\equiv q\to p$

Inverse

The inverse of $p\to q$ is $\sim p\to \sim q$ The inverse of “if p then q” is “if ~p then ~q” $p\to q/\equiv \sim p\to \sim q$

Notes

The converse of a conditional statement $\equiv$ the inverse of the logical statement (They are contrapositive) Summary:

1. conditional statement $\equiv$ contrapositive
2. converse $\equiv$ inverse
3. conditional statement $\not\equiv$ converse

Biconditional (iff)

Statements of the form $p\leftrightarrow q$ ”$p$ if and only if $q$” or ”$p$ iff $q$” ”$p$ is a necessary and sufficient condition for $q$”

$p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$

Logic Connectives

Order of Operations

1. ~ (Not)
2. $\wedge$ and $\vee$ are coequal in order of operation (for CS1231S)
3. $\to$ and $\leftrightarrow$ are coequal in order of operation

Examples

$\sim p\wedge q\equiv (\sim p)\wedge q$ is unambiguous $p\wedge q\vee r$ is ambiguous

Not (Negation)

Symbol

~ (also $\neg$)

Truth Table

p	~p
T	F
F	T

And (Conjuction)

Symbol

$\wedge$

Truth Table

p	q	p $\wedge$ q
T	T	T
T	F	F
F	T	F
F	F	F

Or (Disjunction)

Symbol

$\vee$

Truth Table

p	q	p $\vee$ q
T	T	T
T	F	T
F	T	T
F	F	F

Xor

Symbol

$\oplus$ (Not used for CS1231S) $\oplus \equiv (p\vee q)\wedge \sim (p\wedge q)$

Truth Table

$p$	$q$	$p\vee q$	$p\wedge q$	$\sim (p\wedge q)$	$(p\vee q)\wedge \sim (p\wedge q)$
T	T	T	T	F	F
T	F	T	F	T	T
F	T	T	F	T	T
F	F	F	F	T	F

Implies

Symbol

$\to$

Truth Table

$p$	$q$	$p\to q$
T	T	T
T	F	F
F	T	T
F	F	T

If and Only If

Symbol

$\leftrightarrow$

Truth Table

$p$	$q$	$p\leftrightarrow q$
T	T	T
T	F	F
F	T	F
F	F	T

Logical Equivalence

Definition

Two statements are called logically equivalent iff they have identical truth values for each possible substitution of statements for their statement variables.

Notation

The logical equivalence of statement forms $P$ and $Q$ is denoted by $P\equiv Q$

How to Show Not $\equiv$

There are two ways to show that statement forms $P$ and$Q$ are not logically equivalent:

Truth Table

Find at least one row where their truth values differ

Example

Show that $\sim (p\wedge q)$ and $\sim p\wedge \sim q$ are not logically equivalent

$p$	$q$	$\sim p$	$\sim q$	$p\wedge q$	$\sim (p\wedge q)$	$\sim p\wedge \sim q$
T	T	F	F	T	F	F
T	F	F	T	F	T	F
The last row of the table shows that they are not logically equivalent

Counter example

Find concrete statements for each of the two forms, one of which is true and the other of which is false

Example

Show that $\sim (p\wedge q)$ and $\sim p\wedge \sim q$ are not logically equivalent Let $p$ be true and $q$ be false $\sim (p\wedge q)$ Will evaluate to true $\sim p\wedge \sim q$ Will evaluate to false Therefore, they cannot be logically equivalent

Quantified Statements

These are known as quantifiers

Universal Statement

Definition

Let $Q(x)$ be a predicate and $D$ the domain of $x$ A universal statement is a statement of the form "$\forall x\in D,Q(x)$" i.e. Says that a certain property is true for ALL elements in a set

Example

All positive integers are greater than zero

Keywords

• All
• Every
• Any

Symbol

$\forall$

Negation

Negation of a universal statement (“all are”) $\equiv$ existential statement (“some are not” / “there is at least one that is not”) $\sim (\forall x\in D,P(x))\equiv \exists x\in D\text{ such that}\sim P(x)$

Notes

A value for $x$ for which $Q(x)$ is false is called a counterexample Implicit Quantification: Sometimes, quantification has to be inferred from context

• If $x>2$ then $x^2>4$
• Is interpreted to mean: $\forall$ real numbers $x$, (if $x>2$ then $x^2>4$)

Conditional Statement

Definition

Says that IF one thing is true, THEN another thing also has to be true

Example

If 378 is divisible by 18, then 378 is divisible by 6

Keyword

if … then

Symbol

$\to$

Universal Conditional Statement

Definition

$\forall x(P(x)\to Q(x))$ $\forall x(\text{if }P(x)\text{ then }Q(x))$ Note: if not specified, “for all” is for the whole domain: $\forall x\in D$, where $D$ is the domain of $x$

Equivalent Forms

By changing the domain, a universal conditional statement can be converted to a universal statement: Suppose $\forall x\in U(P(x)\to Q(x))$ By narrowing $U$ to be the set of all values that make $P(x)$ true, set $D$, $\forall x\in D,Q(x)$

Negation

$\sim (\forall x(P(x)\to Q(x)))\equiv \exists x\text{ such that}\sim (P(x)\to Q(x))$ -(A) $\sim (P(x)\to Q(x))\equiv P(x)\wedge \sim Q(x)$ -(B) Substitute (B) into (A) $\sim (\forall x(P(x)\to Q(x)))\equiv \exists x\text{ such that}(P(x)\wedge \sim Q(x))$

Vacuous Truth

$\forall x\in D(P(x)\to Q(x))$ is vacuously true or true by default iff $P(x)$ is false for every $x$ in $D$ (or $D$ is an empty set)

Variants

Variants mentioned in Logical Conditional Statements can be extended to universal conditional statements They follow the same relations to each other (statement $\equiv$ contrapositive etc.)

Existential Statement

Definition

Let $Q(x)$ be a predicate and $D$ the domain of $x$ An existential statement is a statement of the form "$\exists x\in D\text{ such that }Q(x)$" Says that there is at least one thing for which the property is true

Example

There is a prime number that is even

Keywords

• There exists
• There is
• Some

Symbol

$\exists$

Negation

Negation of an existential statement (“some are”) $\equiv$ universal statement (“none are” / “all are not”) $\sim (\exists x\in D\text{ such that }P(x))\equiv \forall x\in D,\sim P(x)$

Notes

$\exists !$ denotes “there exists a unique” or “there is one and only one”

Multiply Quantified Statements

Multiple quantifiers can be used for a single statement e.g. $\forall x\in D,\exists y\in D\text{ such that }P(x,y)$

Negation

Negate statements “from outside in” $\sim (\forall x\in D,\exists y\in E\text{ such that }P(x,y))$ $\equiv \exists x\in D\text{ such that}\sim (\exists y\in E\text{ such that }P(x,y))$ $\equiv \exists x\in D\text{ such that }\forall y\in E,\sim P(x,y)$