Class notes
Algorithmic Foundations Bullet Pointed Key Concepts 2020_2021
- Course
- Institution
- Book
Algorithmic Foundations 2 course's key points summarised. As taught by Dr. Gethin Norman
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
More summaries for
-
Data Structures & Algorithms Lecture Summary
-
Summary Book
Seller
Follow
jimcarty
Content preview
https://en.wikipedia.org/wiki/List_of_mathematical_symbols_by_subjectPropositional 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 )
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller jimcarty. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.86. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67096 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now