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\,\!$	$\neg p$	$p\wedge q$	$p\vee q$	$p\oplus q$	$p\rightarrow 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 {T} \equiv p$ $p\vee \mathbf {F} \equiv p$	Identity laws
$p\vee \mathbf {T} \equiv \mathbf {T}$ $p\wedge \mathbf {F} \equiv F$	Domination laws
$p\vee p\equiv p$ $p\wedge p\equiv p$	Idempotent laws
$\neg (\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
$\neg (p\wedge q)\equiv \neg p\vee \neg q$ $\neg (p\vee q)\equiv \neg p\wedge \neg q$	De Morgan's laws
$p\vee (p\wedge q)\equiv p$ $p\wedge (p\vee q)\equiv p$	Absorption laws
$p\vee \neg p\equiv \mathbf {T}$ $p\wedge \neg p\equiv \mathbf {F}$	Negation laws

Quantifiers

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

Universal Quantification

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

$\forall xP(x)\equiv P(x_{1})\wedge P(x_{2})\wedge \ldots \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,

$\exists xP(x)\equiv P(x_{1})\vee P(x_{2})\vee \ldots \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,

$\exists !xP(x)\equiv P(x_{1})\oplus P(x_{2})\oplus \ldots \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 $\exists x(x+y=1)$, $x$ is bound, but $y$ is free (not bound). To fix this, we would write $\exists x\exists y(x+y=1)$.

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