121 Week 4 - Propositional Logic Flashcards
Proposition
A claim about something that is either true or false
Atomic proposition
A proposition where the outcome only depends on the proposition itself
Compound proposition
A proposition constructed from atomic propositions by combining them with fundamental connectives
Truth table
A table representing the value of a compound proposition for all possible values of its atomic propositions and their combinations.
It has 1 column for each atomic proposition and 1 column for the compound proposition
Fundamental connectives (6)
AND, OR, XOR, NOT, Conditional, Biconditional
AND
Takes 2 propositions (P and Q) to form a third proposition called a conjunction
Conjunction is true when both P and Q are true
Written as P ∧ Q
Can connect many propositions. To be true, all connected propositions must be true
OR
Takes 2 propositions (P and Q) to form a third proposition called a disjunction or inclusive disjunction
Disjunction is true when P or Q or both are true or both are true.
Written as P ∨ Q
Can connect many propositions. To be true, 1 or more connected propositions must be true
XOR
Takes 2 propositions (P and Q) to form a third proposition called an exclusive disjunction
Exclusive disjunction is only true when only P is true or only Q is true.
Written as P ⊕ Q or P ⊻ Q
Can connect many propositions. To be true, an odd number of connected propositions must be true. If an odd number of propositions are true, the exclusive disjunction is false
NOT
Takes a single proposition (P) to form a second proposition called negation
Negation is true when P is false
Written as ~P
Conditional
Consists of the antecedent (P) and consequent (Q)
IF antecedent THEN consequent
Conditional is only false if the antecedent is true but the consequent is false
Written as P → Q
Biconditional
Combines 2 propositions P and Q to form a third proposition called biconditional
Antecedant if and only if consequent OR consequent if and only if antecedant
Biconditional is true when both P and Q have the same value.
Written as P ↔ Q
Equivalent to (P → Q) ∧ (Q → P)
Order of precedence for connecting multiple different connectives
NOT, AND, OR, Conditional, Biconditional
Tautologies
Propositions which are always true, regardless of the truth values of its atomic propositions
Contradictions
Propositions which are always false, regardless of the truth values of its atomic propositions
Contingencies
Propositions that are neither tautologies nor contradictions
Equivalence
Propositions that have exactly the same truth value under all circumstances
Argument
A sequence of propositions (called premises) that end with a conclusion.
Arguments are valid if given that the premises are true, then the conclusion is also true.
Premises
The basis on which we try to establish the conclusion
Conclusion
The claim that we are trying to establish as true
Rules
Functions which take some propositions as premises and returns others as conclusions
Inference rules
Logical rules that allow us to derive new propositions (conclusions) from a set of premises. They serve as the building blocks of logical reasoning.
What are the different inference rules (7)
modus ponens, modus tollens, addition, simplification, hypothetical syllogism, disjunctive syllogism, absorption.
Modus ponens
If a conditional statement is true, and its antecedent is true, then its consequent must also be true.
If p → q and p, then q.
Modus tollens
If a conditional statement is true, and its consequent is false, then its antecedent must also be false.
If p → q and ¬q, then ¬p.
Addition
If a statement is true, then the disjunction of that statement with any other statement is also true.
If p, then p ∨ q
Simplification
If a conjunction is true, then each of its conjuncts is also true.
If p ∧ q, then p
If p ∧ q, then q
Hypothetical syllogism
If two conditional statements are true, where the consequent of the first is the antecedent of the second, then a third conditional statement combining the antecedent of the first and the consequent of the second is also true.
Form: If p → q and q → r, then p → r.
Disjunctive syllogism
If a disjunction or exclusive disjunction is true, and one of the disjuncts (the parts of the or statement) is false, then the other disjunct must be true.
If p ∨ q and ¬p, then q.
Absorption
If a conditional statement is true then if the antecedent is true then both the antecedent and consequent must be true.
if p → q then p → (p ∧ q)
Replacement rules
Rules for replacing parts of propositions with logically equivalent expressions
What are the replacement rules? (12)
Commutative law,
Associative law,
Distributive law,
De Morgan’s laws,
Absorption law,
Identity law,
Idempotence law,
Negation law,
Double negation law,
Implication law,
Contraposition law,
Equivalence law.
Commutative law
The propositions does not affect the result of the conjunction or disjunction
P ∧ Q = Q ∧ P
P v Q = Q v P
Associative law
The grouping of the propositions does not affect the result of the conjunction or disjunction
(P v Q) v R = P v (Q v R)
(P ∧ Q) ∧ R = P ∧ (Q ∧ R)
Distributive law
Distribution (or separate application) of conjunction over disjunction; or distribution of disjunction over conjunction.
P ∧ (Q v R) = (P ∧ Q) v (P ∧ R)
P v (Q ∧ R) = (P v Q) ∧ (P ∧ R)
De Morgan’s laws
The conjunction of negations is the negation of a disjunction
~P ∧ ~Q = ~(P v Q)
The disjunction of negations is the negation of a conjunction
~P v ~Q = ~(P ∧ Q)
Absorption law
The disjunction of any proposition P with (P ∧ Q) has the same truth value as P
P ∨ (P ∧ Q) = P
The conjunction of any proposition P with (P ∨ Q) has the same truth value as P
P ∧ (P ∨ Q) = P
Identity law
the conjunction of any proposition P with an arbitrary tautology T (proposition which is always true) has the same truth value as P
P ∧ T = P
the disjunction of any proposition P with an arbitrary contradiction F (proposition which is always false) has the same truth value as P
P ∨ F = P
Idempotence law
the property of a conjunction or disjunction to be applied multiple times on a proposition without changing the proposition
P ∧ P is equivalent to P
P ∨ P is equivalent to P
Negation law
the disjunction of any proposition P and its negation is a tautology
P ∨ ~P is a tautology
the conjunction of any proposition P and its negation is a contradiction
P ∧ ~P is a contradiction
Double negation law
Any proposition with 2 NOTs is the same as just the proposition.
~~P = P
Implication law
Implication can be expressed by disjunction and negation
P → Q = ~P ∨ Q
Contraposition law
A conditional P → Q is equivalent to its contrapositive (implication of negations): ~Q → ~P
P → Q = ~Q → ~P
Equivalence law
A biconditional P <-> Q is equivalent to the conjunction of two conditionals: (P → Q) ∧ (Q → P)
P <-> Q = (P → Q) ∧ (Q → P)
