CSCE 222 Chapter 1.1

« previous | Wednesday, February 9, 2011 | next »

Propositional Logic

A proposition is a declarative sentence that is either true or false (but not both)

represented by a small letter "propositional variable" (usually $p$, $q$, $r$, etc.)

Logical Connectives

(in order of precedence)

Connective	Symbol	English Value	Read as
Negation	¬	"It is not the case that…"	"not $p$"
Conjunction	∧	"and", "but"	"$p$ and $q$"
Disjunction	∨	"or"	"$p$ or $q$"
Exclusive or	⊕	"either $p$ or $q$"	"$p$ ex-or $q$"
Conditional	→	"if $p$, [then] $q$", "$p$ is sufficient for $q$", "$q$ if $p$", "$q$ unless ¬$p$", "$p$ implies $q$", "$p$ only if $q$", "$q$ whenever $p$", "$q$ is necessary for $p$", "$q$ follows from $p$"	"$p$ implies $q$"
Biconditional	↔	"$p$ is necessary and sufficient for $q$", "$p$ if and only if $q$"	"$p$ if and only if $q$"

Truth Table of Connectives

$p$	$q$	$\mathrm{\neg }p$	$p\wedge q$	$p\vee q$	$p\oplus q$	$p\to q$	$p\leftrightarrow q$
T	T	F	T	T	F	T	T
T	F	F	F	T	T	F	F
F	T	T	F	T	T	T	F
F	F	T	F	F	F	T	T

Conditionals

• given conditional: p → q
• converse: q → p
• inverse: ¬p → ¬q
• contrapositive: ¬q → ¬p

Logical Equivalence

two statements are logically equivalent if and only if they have the same truth table.

Equivalence	Name
$p\wedge \mathbf{𝐓}\equiv p$ $p\vee \mathbf{𝐅}\equiv p$	Identity laws
$p\vee \mathbf{𝐓}\equiv \mathbf{𝐓}$ $p\wedge \mathbf{𝐅}\equiv F$	Domination laws
$p\vee p\equiv p$ $p\wedge p\equiv p$	Idempotent laws
$\mathrm{\neg }(\mathrm{\neg }p)\equiv p$	Double negation law
$p\vee q\equiv q\vee p$ $p\wedge q\equiv q\wedge p$	Commutative laws
$(p\vee q)\vee r\equiv p\vee (q\vee r)$ $(p\wedge q)\wedge r\equiv p\wedge (q\wedge r)$	Associative 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)$	Distributive laws
$\mathrm{\neg }(p\wedge q)\equiv \mathrm{\neg }p\vee \mathrm{\neg }q$ $\mathrm{\neg }(p\vee q)\equiv \mathrm{\neg }p\wedge \mathrm{\neg }q$	De Morgan's laws
$p\vee (p\wedge q)\equiv p$ $p\wedge (p\vee q)\equiv p$	Absorption laws
$p\vee \mathrm{\neg }p\equiv \mathbf{𝐓}$ $p\wedge \mathrm{\neg }p\equiv \mathbf{𝐅}$	Negation laws

Quantifiers

• Higher precedence than all logical operators
• Distribute across parenthesized terms: $\mathrm{\forall }x(P(x)\wedge Q(x))\equiv \mathrm{\forall }xP(x)\wedge \mathrm{\forall }xQ(x)$

Universal Quantification

If a predicate $P(x)$ is true for all values of $x$ in the domain,

$\mathrm{\forall }xP(x)\equiv P(x_1)\wedge P(x_2)\wedge \dots \wedge P(x_n)$

To be contradicted, we need to find only one value of $x$ such that $P(x)$ is false.

Existential Quantification

If a predicate $P(x)$ is satisfiable for at least one value of $x$ in the domain,

$\mathrm{\exists }xP(x)\equiv P(x_1)\vee P(x_2)\vee \dots \vee P(x_n)$

To be contradicted, every value of $x$ has to be false.

Unique Quantification

If a predicate $P(x)$ is satisfiable for only one value of $x$ in the domain,

$\mathrm{\exists }!xP(x)\equiv P(x_1)\oplus P(x_2)\oplus \dots \oplus P(x_n)$

To be contradicted, more than one $x$ has to be true or all values of $x$ evaluate to be false.

Variable Binding

A variable is bound if a quantifier is used on that variable. A bound variable does not mean anything outside of the quantification. For example, in $\mathrm{\exists }x(x+y=1)$, $x$ is bound, but $y$ is free (not bound). To fix this, we would write $\mathrm{\exists }x\mathrm{\exists }y(x+y=1)$.

In the statement $\mathrm{\forall }xP(x)\wedge \mathrm{\forall }xQ(x)$, the two bound $x$ variables are not related whatsoever.