College aantekeningen
Algorithmic Foundations Bullet Pointed Key Concepts 2020_2021
- Vak
- Instelling
- Boek
Algorithmic Foundations 2 course's key points summarised. As taught by Dr. Gethin Norman
[Meer zien]Voorbeeld 4 van de 47 pagina's
Voorbeeld 4 van de 47 pagina's
In winkelwagen
In winkelwagen
gesponsord bericht van onze partner
Gekoppeld boek
Titel boek:
Auteur(s):
- Uitgave:
- ISBN:
- Druk:
Meer samenvattingen voor studieboek
-
Datastructuren deel 1
-
Data Structures & Algorithms Lecture Summary
-
Summary Book
Verkoper
Volgen
jimcarty
Voorbeeld van de inhoud
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 )
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper jimcarty. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €3,69. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 67096 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen