Algorithmic Foundations Bullet Pointed Key Concepts 2020_2021

https://en.wikipedia.org/wiki/List_of_mathematical_symbols_by_subject

Propositional logic
● Logic of compound statements built from simpler statements using boolean connectives
Propositions
● Building blocks of logic
● Either true or false
○ ( 1 + 1 ) == 2
● Propositional logic/calculus
● Not a propositional
○ ( x + 1 ) == 2; depends on value of x and is there for either true or false
● Syntax :
○ Let p be the proportion “today is Friday”
Connectives
● Created by combining one or more propositions
● Compound propositions/formulae
● Capital letter used to denote
● Truth tables
○ Displays relationships between truth value of a formulae and the truth values of
the propositions
○ Listed in binary from 0, 1, 10, 11, 100, 101, etc.
● Examples
○ Negation ( not )
■ Let p be the proposition “today is Friday”
■ Then ¬p is the proposition “it is not Friday”
○ Conjunction ( and )
■ Let p be the proportion “today is Friday”
■ Let q be the proposition “it is raining”
■ Then p∧q is the proposition “today is Friday and it is raining”
○ Disjunction ( or )
■ Let p be the proportion “today is Friday”
■ Let q be the proposition “it is raining”
■ Then p∨q is the proposition “today is Friday or it is raining”
○ Exclusive Or ( xor )
■ Let p be the proportion “today is Friday”
■ Let q be the proposition “it is raining”
■ Then p⊕q is the proposition “today is Friday or it is raining but
not both”
○ Implications ( implies )
■ Let p be the proportion “today is Friday”
■ Let q be the proposition “it is raining”
■ Then p→q is the proportion “if it is Friday then it is raining”
■ q = p→q or if p and q == 0 then p→q = 1
■ p→q is only false when contract is broken

, ■ Another example
■ Let p be the proportion “if it is sunny”
■ Let q be the proposition “you will take me to the beach”
■ Only then it is sunny but you did not take me to the beach
is the contract broken and p→q is false
■ Relational implications
■ Converse : q→p
■ The contract is flipped
■ “If you take me to the beach then it is sunny”
■ Equivalent to the inverse
■ Contrapositive : ¬q→¬p
■ Negate both and then the contract is flipped
■ “If you do not take me to the beach then it is not sunny”
■ Is the equivalent to original implication
■ Inverse : ¬p→¬q
■ Negate both and the contract stays the same
■ “If it isn’t sunny you won’t take me to the beach”
■ Contrapositive of the converse
■ Equivalent to the converse
○ Biconditional ( if and only if )
■ Let p be the proportion “today is Friday”
■ Let q be the proposition “it is raining”
■ Then p↔q is the proposition “today is Friday if and only if it is
raining”
■ For p↔q to hold, either p and q are both false or both true
○ Precedence
■ If (p∨q)∧r is true, then p or q is true, and r is true
■ If p∨(q∧r) is true, then either p is true or q and r are true
■ BODMAS
■ Negation is applied before all else
■ Conjunction
■ Disjunction
■ Implication
■ Biconditional
■ When in doubt, use parenthesis
○ Tautology ( is always true )
■ Classic examples :
■ p→p
■ p∨¬p
○ Contradiction ( is always false )
■ Classic examples :
■ p∧¬p
○ Contingency ( neither a tautology or a contradiction )
■ I.e everything else

, ■ p∧q
■ p∨q
■ p→q; etc.
○ Satisfiable
■ If there is a condition in which the values of the propositions makes the
formula true
■ i.e it is not a contradiction
Logical equivalence
● Two different compound propositions but have the same meaning ( semantically
identical )
● P≡Q
● Proven
○ Laws of logical equivalence
○ Truth columns
■ 2^n where n is number of propositions
● Proven not
○ Give one assignment that shows that one returns true and one returns false
Laws of logical equivalence
● x·0 = 0
● x·1 = x
● x+y=y+x
● x·( y + z ) = x·y + x·z
● x+(y+z)=(x+y)+z
● Identity laws
○ P ∧ true ≡ P
○ P ∨ false ≡ P
● Domination laws
○ P ∨ true ≡ true
○ P ∧ false ≡ false
● Idempotent laws
○ P∧P≡P
○ P∨P≡P
● Double negation law
○ ¬(¬P) ≡ P
● Commutative laws
○ P∨Q≡Q∨P
○ P∧Q≡Q∧P
● Associative laws
○ (P∨Q)∨R≡P∨(P∨R)
○ (P∧Q)∧R≡P∧(P∧R)
● Distributive laws
○ P ∨ ( Q ∧ R ) ≡ ( P ∨ Q ) ∧ ( P ∨ R)
○ P ∧ ( Q ∨ R ) ≡ ( P ∧ Q ) ∨ ( P ∧ R)
● De Morgan’s laws

, ○ ¬( P ∨ Q ) ≡ ¬P ∧ ¬Q
○ ¬( P ∧ Q ) ≡ ¬P ∨ ¬Q
● Contradiction and tautology laws
○ P ∧ ¬P ≡ false
○ P ∨ ¬P ≡ true
● Implication law
○ P → Q ≡ ¬P ∨ Q
● We can define disjunction using conjunction and negation
● We can define disjunction and conjunction using implication and negation
● P → false ≡ ¬P
● Examples
○ ( P ∧ Q ) → ( P ∨ Q ) ≡ true
○ ¬( P ∨ ( ¬P ∧ Q ) ) ≡ ¬P ∧ ¬Q
Predicate logic
● Foundation of all mathematical logic which reveals the ultimate limits of mathematical
thought
● We cannot discover all mathematical truths unless we resort to making a guess
● Specifying statements that involve variables
○ x>3
○ Neither true of false
○ Predicates allows us to construct propositions using variables
Predicates
● Mapping from some domain U to truth values
● P : U → { true, false }
● For any element x of U, we have P(x) is either true or false
● Example
○ Let U equal the set of integers ℤ = { …, -2, -1, 0, 1, 2, … } and let the predicate
P(x) be given by x > 0
■ P( -2 ) is false
■ P( 42 ) is true
■ P( 0 ) is false
○ Let the predicate Q( x, y ) be given by x > y
■ Q( 1, 2 ) is false
■ Q( 2, 1 ) is true
○ Let the predicate R( x, y, z ) be given by x+y+z=4
■ R( 1, 1, 1 ) is false
■ R( 1, 1, 2 ) is true
● A predicate is a Boolean function
○ Delivers either true or false
■ isOdd( x ), isEven( x )
● Predicates become compound propositions if
○ Variables are assigned values; or,
○ Variables are bound with values from its domain U through quantifiers
● In the predicate P( y )