Please enable JavaScript.
Coggle requires JavaScript to display documents.
Propositional calculus (Laws of logic (Direct and inverse theorems…
Propositional calculus
Proposition
Statement
True or false
No middle ground
Only concerned with true or false value
Logical connectives
Way of constructing complex statements
From simple ones
Conjunction: \(x\land y\)
True if and only if both \(x\) and \(y\) are true.
\(\begin{array}{c|c|c}x & y & x \land y \\ \hline t & t & t\\ t & f & f\\ f & t & f\\ f& f& f\end{array}\)
AND: \(\land\)
Disjunction: \(x \lor y\)
False if and only if each of \(x\) or \(y\) are false
OR: \(\lor\)
\(\begin{array}{c|c|c}x & y & x \lor y \\ \hline t & t & t \\ t & f & t \\ f & t & t \\ f & f & f \end{array}\)
Implication: \(x \to y\)
If (assumption) then (consequence)
\(\to\)
False if and only if assumption true and consequence false
Think about how to break a promise
If the moon is made of cheese I will give you £100
\(\begin{array}{c|c|c}x & y & x \to y\\ \hline t & t & t \\ t & f & f \\ f & t & t \\ f & f & t \end{array}\)
Negation: \(\lnot x\)
NOT: \(\lnot\)
True if and only if \(x\) is false
\(\begin{array}{c|c}x & \lnot x \\ \hline t & f \\ f & t\end{array}\)
Boolean or propositional formulae
Given a collection of variables \(X_1, X_2, \ldots X_n\) a Boolean formula is a string from the set \(\{X_1,X_2,\ldots, X_n, \land, \lor, \lnot, \to, (, )\}\)
such that
any variable, \(X_i, 1 \leq i \leq n\), is a formulae
If \(F\) and \(G\) are formula so are:
\((F\land G)\)
\((F\lor G)\)
\((F\to G)\)
\(\lnot F\)
\(\lnot G\)
For example
\((X\to \lnot Y) \lor (\lnot Z \land Y)\) is a formula
\((X \to))\) is not a formula
Can be computed by replacing
variables with \(t\) or \(f\)
Truth tables give the outcome in all situations
Tautologies, identically true
A formula which is true for all possible
assignments of \(t\) and \(f\) to the variables
Could use a truth table
Could use a logical argument
True regardless of value of variable
e.g. \(X \lor \lnot X\)
So can substitute any formulae
for a variable e.g. setting \(X = (Y \to Z)\)
we get \((Y\to Z) \lor \lnot(Y \to Z)\)
For example
\(X\lor \lnot X\)
\(\lnot\lnot X \to X\)
\(X\to \lnot\lnot X\)
\(\lnot(X\land \lnot X)\)
\((\lnot X \to Y)\land (\lnot X\to \lnot Y)\to X\)
Logically equivalent: \(F \equiv G\)
True if and only if \(F\) and \(G\)
have the same truth value
Abbreviation for
\((F \to G) \land (G \to F)\)
\(\begin{array}{c|c|c} x & y & x \equiv y\\ \hline t & t & t \\ t & f & f \\ f & t & f \\ f & f & t\end{array}\)
Laws of logic
Are tautologies
Can be proved by truth table
For variable \(X, Y, Z\) the following are true
Commutative
\((X\land Y)\equiv (Y \land X)\)
\((X\lor Y)\equiv (Y\lor X)\)
Associative
\(((X\land Y)\land Z)\equiv (X\land(Y\land Z))\)
\(((X \lor Y)\lor Z)\equiv (X \lor (Y\lor Z))\)
Distributive
Conjunction over disjunction:
\((X\land (Y \lor Z))\equiv ((X\land Y)\lor (X \land Z))\)
Disjunction over conjunction:
\((X\lor (Y \land Z)) \equiv ((X \lor Y) \land (X\lor Z))\)
de Morgan's laws
\(\lnot (X\land Y) \equiv (\lnot X \lor \lnot Y)\)
\(\lnot (X \lor Y)\equiv (\lnot X \land \lnot Y)\)
Unnamed laws
No middle ground:
\(X\lor \lnot X\)
Every proposition is true or false
Same as \(\lnot(X\land \lnot X)\)
Double negative:
\(\lnot\lnot X\equiv X\)
Useful if need to do without a particular connective
when combined with de Morgan's laws e.g. can express or in terms of and and vice versa:
\(U\lor V \equiv \lnot\lnot U \lor \lnot\lnot V \equiv \lnot (\lnot U \land \lnot V)\)
Getting rid of implies:
\((X\to Y)\equiv (\lnot X \lor Y)\)
Reductio ad absurdum
\(((\lnot X \to Y)\land(\lnot X \to \lnot Y))\to X\)
Proof by contradiction:
If I want to prove a proposition \(X\) it is sufficient to
assume the negative \(\lnot X\) is true and
deduce from this two contradictory statements
\(Y\) and \(\lnot Y\) which is impossible.
Hence we conclude \(X\) must be true.
Direct and
inverse theorems
Direct theorem: \(X\to Y\)
If \(X\) then \(Y\)
\(X\) is the sufficient condition
\(Y\) is the necessary condition
Inverse theorem: \(Y\to X\)
THIS IS NOT equivalent to
the direct theorem!
"\(X\) is necessary and sufficient for \(Y\)"
means both the direct, \(X\to Y\)
and the inverse \(Y\to X\) are true.
Opposite theorem: \(\lnot X \to \lnot Y\)
THIS IS NOT equivalent to
the direct theorem!
Opposite to inverse theorem: \(\lnot Y \to \lnot X\)
THIS IS equivalent to
the direct theorem since
\((X \to Y) \equiv (\lnot Y \to \lnot X)\)
Might be easier to prove
than the direct theorem
Normal forms
Variables: \(X_1, X_2,\ldots, X_n\)
Literals: \(Y_i = X_i\) or \(Y_i = \lnot X_i\) for any \(i\)
Terms: If for \(i_j \in \{1, 2, \ldots, n\}\),
and \(1 \leq j \leq m\) then \(Y_{i_j}\) is a literal then
A conjunctive term is a conjunction of literals:
\(Y_{i_1} \land Y_{i_2} \land \cdots \land Y_{i_m}\)
A disjunctive term is a disjunction of literals:
\(Y_{i_1} \lor Y_{i_2} \lor \cdots \lor Y_{i_m}\)
Disjunctive Normal Form (DNF) has the form \(F_1 \lor F_2 \lor \cdots \lor F_n\) where \(F_i\) are CONJUNCTIVE terms
Method: Use laws to manipulate the formula
Get rid of implies
Create conjunctions using logical laws e.g. the distributive and de Morgan's. Sometimes need clever tricks e.g. since we know \(X \land \lnot X\) is always false we can conclude \((X \land \lnot X) \lor (X \land \lnot Y) \equiv (X\land \lnot Y)\)
Example:
\(\begin{eqnarray*} &&((\lnot X \to Y) \land (\lnot X \to \lnot Y)) \to X \\ &&\equiv \lnot ((X \lor Y)\land (X \lor \lnot Y))\lor X \text{ since } F \to G \equiv \lnot F \lor G \\ &&\equiv \lnot(X\lor Y) \lor \lnot (X\lor \lnot Y) \lor X \text{ by de Morgan's laws} \\ &&\equiv (\lnot X \land \lnot Y)\lor (\lnot X \land Y) \lor X \text{ by de Morgan's laws} \end{eqnarray*}\)
Theorem: Every Boolean Formula is equivalent to one in DNF
Proof: Not in this unit
Conjunctive Normal Form (CNF)
has the form \(F_1 \land F_2 \land \cdots \land F_n\)
where \(F_i\) are DISJUNCTIVE terms
Theorem: Every Boolean Formula is equivalent to one in CNF
Proof: Not in this unit
Sets
Consists of elements
Finite or infinite in size
Empty set: \(\emptyset\) has size 0
and contains NO elements
Notation:
\(a \in S\) means \(a\) is an element of \(S\)
\(a \not\in S\) means \(a\) is NOT an element of \(S\)
Example:
\(S = \{a, b, c\}\)
is a set called \(S\) which contains
elements \(a, b\) and \(c\).
Quantifiers
Predicate
Variable proposition
Depends on one
of more variables
Possible values belong to a set
Can substitute in
for variables
Turns a predicate
into a proposition
Universal quantifier: \(\forall\)
For all (variable in set) (predicate)
\(\forall x \in S (\ldots)\)
Example
\(\forall x \in \{-1,0,1\} (x+1 > x)\)
\((-1+1 > -1) \land (0 + 1 > 0) \land (1 + 1 > 1)\)
Existential quantifier: \(\exists\)
These exists (variable in set) (predicate)
\(\exists x \in S (\ldots)\)
Example
\(\exists x \in \{-1,0,1\} (x \leq 0)\)
\((-1 \leq 0) \lor (0 \leq 0) \lor (1 \leq 0)\)
Formulae containing both
Think carefully!
\(\forall x \in \{0,1\} \exists y \in \{0,1\} (x+y = 0)\)
is a conjunction of disjunctions:
\(((0+0 = 0) \lor (0+1 = 0)) \land ((1 + 0 = 1) \lor (1+1 = 0))\)
Negation
Generalises de Morgan's laws
\(M\) a set and \(P(x)\) a predicate
\(\lnot (\forall x \in M~ P(x)) \equiv (\exists x \in M~ (\lnot P(x)))\)
\(\lnot (\exists x \in M~ P(x)) \equiv (\forall x \in M~ (\lnot P(x)))\)
Examples
\(\lnot (\forall x \in \mathbb{Z} ~ (x+1 > x)) \equiv (\exists x \in \mathbb{Z} ~ (x + 1 \leq x))\)
\(\lnot (\exists x \in \mathbb{Z} ~ (x < 0)) \equiv (\forall x \in \mathbb{Z} ~ (x \geq 0))\)
\(\lnot (\forall x \in M ~ \exists y \in N ~ P(x,y)) \equiv (\exists x \in M ~ \forall y \in N ~ \lnot P(x,y))\)