2. Logic

2.1 Propositions and logical operations

Logic: the study of formal reasoning
Proposition: a statement that is either true or false (not a command or a question)
Proposition’s truth value: a value indicating whether the proposition is true or false
Proposition variables: denote arbitrary propositions
Compound proposition: connecting individual propositions with logical operations
Logical operation: combines propositions using a particular composition rule
Conjunction: $\wedge$
Truth table: shows the truth value of a compound proposition for every possible combination of truth values for the variables in the compound proposition
Disjunction (inclusive or): $\vee$
Exclusive or: $\oplus$
Negation: $\neg$

2.2 Evaluating compound propositions

Order of operations without parentheses:

1. $\neg$
2. $\wedge$
3. $\vee$

2.3 Conditional statements

Conditional operation: $\Rightarrow$
Conditional proposition: a compound proposition that uses a conditional operation

In $p\Rightarrow q$,
Hypothesis: $p$
Conclusion: $q$

ONLY IF: necessary condition
IF: sufficient condition

Ex., let:
$p$: I share cookie
$q$: You share soda
$p\Rightarrow q$: I share cookie ONLY IF you share soda.
$\neg q\Rightarrow \neg p$: I will NOT share cookie if you do NOT share soda.

Proposition	$p\Rightarrow q$
Converse	$q\Rightarrow p$
Contrapositive	$\neg q\Rightarrow \neg p$
Inverse	$\neg p\Rightarrow \neg q$

Biconditional operation (if and only if, necessary and sufficient for): $p⟺q$

Apply $\neg$, $\wedge$, and $\vee$ before $\Rightarrow$ or $⟺$

2.4 Logical equivalence

Tautology: the compound proposition is always true
Contradition: the compound proposition is always false

Not a tautology: find one case where it is false
Not a contradiction: find one case where it is true

Logical equivalence ($\equiv$): two compound propositions have the same truth value regardless of the truth values of their individual propositions

Not logically equivalent: find one case where they have different truth values

First De Morgan’s law: $\neg (p\vee q)\equiv (\neg p\wedge \neg q)$
Second De Morgan’s law: $\neg (p\wedge q)\equiv (\neg p\vee \neg q)$

2.5 Laws of propositional logic

Law	Disjunction Form	Conjunction Form
Idempotent laws	$p\vee p\equiv p$	$p\wedge p\equiv p$
Associative laws	$(p\vee q)\vee r\equiv p\vee (q\vee r)$	$(p\wedge q)\wedge r\equiv p\wedge (q\wedge r)$
Commutative laws	$p\vee q\equiv q\vee p$	$p\wedge q\equiv q\wedge p$
Distributive laws	$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$	$p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$
Identity laws	$p\vee \mathbf{F}\equiv p$	$p\wedge \mathbf{T}\equiv p$
Domination laws	$p\wedge \mathbf{F}\equiv \mathbf{F}$	$p\vee \mathbf{T}\equiv \mathbf{T}$
Double negation law	$\neg \neg p\equiv p$
Complement laws	$p\wedge \neg p\equiv \mathbf{F}$ $\neg \mathbf{T}\equiv \mathbf{F}$	$p\vee \neg p\equiv \mathbf{T}$ $\neg \mathbf{F}\equiv \mathbf{T}$
De Morgan’s laws	$\neg (p\vee q)\equiv \neg p\wedge \neg q$	$\neg (p\wedge q)\equiv \neg p\vee \neg q$
Absorption laws	$p\vee (p\wedge q)\equiv p$	$p\wedge (p\vee q)\equiv p$
Conditional identities	$p\Rightarrow q\equiv \neg p\vee q$	$p\iff q\equiv (p\Rightarrow q)\wedge (q\Rightarrow p)$

2.6 Predicates and quantifiers

Predicate: a logical statement with a truth value that is a function of one or more variables (even if true for all values in the domain)
Domian of a variable in a predicate: the set of possible values for the variable
Universal quantifier: $\forall$
Universally quantified statement: $\forall xP(x)$

NOTE: to turn a predicate into a proposition, either assign values to its variables or use quantifiers

A counterexample for a universally quantified statement: an element in the domain for which the predicate is false

NOTE: if domain of $x$ is empty, then the statement $\forall xP(x)$ is true because there are no elements int he domian for which $P(x)$ is false

Existential quantifier: $\exists$
Existentially quantified statement: $\exists xP(x)$

An example for an existentially quantified statement: an element in the domain for which the predicate is true

NOTE: if domian of $x$ is empty, then the statement $\exists xP(x)$ is false becuase there is no element in the domain for which $P(x)$ is true

2.7 Quantified statements

Quantified statement: a logical statement that includes a universal or existential quantifier

Quantifiers are applied before logical operations

Free variable: a variable $x$ in the predicate $P(x)$
Bound variable: a variable $x$ in the statement $\forall xP(x)$

Scope of a quantifier: the part of the logical expression to which the quantifier applies

A variable name can be reused, as long as the scopes of the quantifiers that bind the variables do not overlap

NOTE: changing someone to everyone usually changes both the quantifier and the operator

• Someone who is A is B: $\exists x(A(x)\wedge B(x))$
• Everyone who is A is B: $\forall x(A(x)\to B(x))$

2.8 De Morgan’s law for quantified statements

De Morgan’s laws for quantified statements
$\neg \forall xP(x)\equiv \exists x\neg P(x)$
$\neg \exists xP(x)\equiv \forall x\neg P(x)$

2.9 Nested quantifiers

Nested quantifiers: a logical expression with more than one quantifier that binds different variables in the same predicate

Two quantifiers of the same type that are next to each other in a logical expression can be switched to obtain a logically equivalent expression

$\neg \forall x\forall yP(x,y)\equiv \exists x\exists y\neg P(x,y)$
$\neg \forall x\exists yP(x,y)\equiv \exists x\forall y\neg P(x,y)$
$\neg \exists x\forall yP(x,y)\equiv \forall x\exists y\neg P(x,y)$
$\neg \exists x\exists yP(x,y)\equiv \forall x\forall y\neg P(x,y)$

2.10 More nested quantified statements

Ex., let:
$M(x,y)$: whether $x$ sent an email to $y$
Everyone sent an email to someone else: $\forall x\exists y((x\ne y)\wedge M(x,y))$

Ex., let:
$L(x)$: whether or not $x$ came late
Exactly one person was late: $\exists x(L(x)\wedge \forall y((x\ne y)\Rightarrow \neg L(y)))$
Someone $x$ who came late and everyone other than $x$ did not come late

Null qualification
$A\wedge \forall xP(x,\ast )\equiv \forall x(A\wedge P(x,\ast )$

NOTE: remember to verify that $x$ does not appear in $A$

Ex.,
$\exists x(L(x)\wedge \forall y((x\ne y)\Rightarrow \neg L(y)))\equiv \exists x\forall y(L(x)\wedge ((x\ne y)\Rightarrow L(y)))$

Ex., let:
$P(x)$: $x$ passed the exam
Everyone other than Alex: $\forall x((x\ne \text{Alex})\to P(x))$

• Every person except Alex must satisfy $P(x)$
• When $x=\text{Alex}$, $x\ne \text{Alex}$ is false, so the implication is automatically true
• Therefore, whether Alex passed is irrelevant
  Everyone: $\forall xP(x)$
• Every person, including Alex, must satisfy $P(x)$
  Key: “Other than Alex” means Alex is not required to pass; it does not mean Alex is required to fail
  To explicitly say Alex did not pass:
  $\forall x((x\ne \text{Alex})\to P(x))\wedge \neg P(\text{Alex})$

2.11 Set notation and quantified logical statements

Define domian before logical expression: $x\in {\mathbb{Z}}^{+},\exists xP(x)$
Inline: the set used in an inline definition of a domian must be explicitly defined beforehand or must use a standard symbol for a methematical set (Ex., $\exists x\in {\mathbb{Z}}^{+},P(x)$)
Multiple variables inline: $\forall x\in \mathbb{R},\exists y\in \mathbb{Z},P(x,y)$