121 Week 4 - Propositional Logic (WIP)

Question 1

Proposition

Answer 1

A claim about something that is either true or false

Question 2

Atomic proposition

Answer 2

A proposition where the outcome only depends on the proposition itself

Question 3

Compound proposition

Answer 3

A proposition constructed from atomic propositions by combining them with fundamental connectives

Question 4

Truth table

Answer 4

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

Question 5

Fundamental connectives (6)

Answer 5

AND, OR, XOR, NOT, Conditional, Biconditional

Question 6

AND

Answer 6

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

Question 7

OR

Answer 7

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

Question 8

XOR

Answer 8

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

Question 9

NOT

Answer 9

Takes a single proposition (P) to form a second proposition called negation
Negation is true when P is false
Written as ~P

Question 10

Conditional

Answer 10

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

Question 11

Biconditional

Answer 11

Combines 2 propositions P and Q to form a third proposition called biconditional
Biconditional is true when both P and Q have the same value.
Written as P ↔ Q
Equivalent to (P → Q) ∧ (Q → P)

Question 12

Order of precedence for connecting multiple different connectives

Answer 12

NOT, AND, OR, Conditional, Biconditional

Question 13

Tautologies

Answer 13

Propositions which are always true, regardless of the truth values of its atomic propositions

Question 14

Contradictions

Answer 14

Propositions which are always false, regardless of the truth values of its atomic propositions

Question 15

Contingencies

Answer 15

Propositions that are neither tautologies nor contradictions

Question 16

Equivalence

Answer 16

Propositions that have exactly the same truth value under all circumstances

Question 17

Argument

Answer 17

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.

Question 18

Premises

Answer 18

The basis on which we try to establish the conclusion

Question 19

Conclusion

Answer 19

The claim that we are trying to establish as true

Question 20

Rules

Answer 20

Functions which take some propositions as premises and returns others as conclusions

Question 21

Inference rules

Answer 21

Logical rules that allow us to derive new propositions (conclusions) from a set of premises. They serve as the building blocks of logical reasoning.

Question 22

What are the different inference rules (7)

Answer 22

modus ponens, modus tollens, addition, simplification, hypothetical syllogism, disjunctive syllogism, absorption.

Question 23

Modus ponens

Answer 23

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.

Question 24

Modus tollens

Answer 24

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.

Question 25

Addition

Answer 25

If a statement is true, then the disjunction of that statement with any other statement is also true.
If p, then p ∨ q

Question 26

Simplification

Answer 26

If a conjunction is true, then each of its conjuncts is also true.
If p ∧ q, then p
If p ∧ q, then q

Question 27

Hypothetical syllogism

Answer 27

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.

Question 28

Disjunctive syllogism

Answer 28

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.

Question 29

Absorption

Answer 29

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)

Question 30

Replacement rules

Answer 30

Rules for replacing parts of propositions with logically equivalent expressions

Question 31

What are the replacement rules? (12)

Answer 31

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.

Question 32

Commutative law

Answer 32

The propositions does not affect the result of the conjunction or disjunction
P ∧ Q = Q ∧ P
P v Q = Q v P

Question 33

Associative law

Answer 33

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)

Question 34

Distributive law

Answer 34

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)

Question 35

De Morgan’s laws

Answer 35

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)

Question 36

Absorption law

Answer 36

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

Question 37

Identity law

Answer 37

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

Question 38

Idempotence law

Answer 38

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

Question 39

Negation law

Answer 39

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

Question 40

Double negation law

Answer 40

Any proposition with 2 NOTs is the same as just the proposition.
~~P = P

Question 41

Implication law

Answer 41

Implication can be expressed by disjunction and negation
P → Q = ~P ∨ Q

Question 42

Contraposition law

Answer 42

A conditional P → Q is equivalent to its contrapositive (implication of negations): ~Q → ~P
P → Q = ~Q → ~P

Question 43

Equivalence law

Answer 43

A biconditional P <-> Q is equivalent to the conjunction of two conditionals: (P → Q) ∧ (Q → P)
P <-> Q = (P → Q) ∧ (Q → P)