which is the following statement pattern is a tautology? 1) [(p->q)^~q]->(~p) 2)[pvq)^~p]^(~q) 2) [p^(p->~q)]->q 3) ~(p->~q)
Answers
Step-by-step explanation:
Negation Introduction (~I – indirect proof IP)
Assume p
Get q & ~q
˫ ~p
Negation Elimination (~E – version of DN)
~~p → p
Conditional Introduction (→I – conditional proof CP)
Assume p
Get q
˫ p → q
Conditional Elimination (→E – modus ponens MP)
p → q
p
˫ q
Conjunction Introduction (&I – conjunction CONJ)
p
q
˫ p & q
Conjunction Elimination (&E – simplification SIMP)
p & q
˫ p
Disjunction Introduction (vI – addition ADD)
p
˫ p v q
Disjunction Elimination (vE – version of CD)
p v q
p → r
q → r
˫ r
Biconditional Introduction (↔I – version of ME)
p → q
q → p
˫ p ↔ q
Biconditional Elimination (↔E – version of ME)
p ↔ q
˫ p → q
or
˫ q → p
IMPORTANT DERIVED RULES OF INFERENCE
Modus Tollens (MT)
p → q
~q
˫ ~P
Hypothetical Syllogism (HS)
p → q
q → r
˫ p → r
Disjunctive Syllogism (DS)
p v q
~p
˫ q
Absorption (ABS)
p → q
˫ p → (p & q)
Constructive Dilemma (CD)
p v q
p → r
q → s
˫ r v s
Repeat (RE)
p
˫ p
Contradiction (CON)
p
~p
˫ Any wff
Theorem Introduction (TI)
Introduce any tautology, e.g., ~(P & ~P)
EQUIVALENCES
De Morgan’s Law (DM)
~(p & q) :: (~p v ~q)
~(p v q) :: (~p & ~q)
Commutation (COM)
(p v q) :: (q v p)
(p & q) :: (q & p)
Association (ASSOC)
[p v (q v r)] :: [(p v q) v r]
[p & (q & r)] :: [(p & q) & r]
Distribution (DIST)
[p & (q v r)] :: [(p & q) v (p & r)]
[p v (q & r)] :: [(p v q) & (p v r)]
Double Negation (DN)
p :: ~~p
Transposition (TRANS)
(p → q) :: (~q→~p)
Material implication (MI)
(p → q) :: (~p v q)
Material Equivalence (ME)
(p ↔ q) :: [(p & q ) v (~p & ~q)]
(p ↔ q) :: [(p → q ) & (q → p)]
Exportation (EXP)
[(p & q) → r] :: [p → (q → r)]
Tautology (TAUT)
p :: (p & p)
p :: (p v p)
Conditional-Biconditional Refutation Tree Rules
~(p → q) :: (p & ~q)
~(p ↔ q) :: [(p & ~q) v (~p & q)]
CATEGORICAL SYLLOGISM RULES
Standard Forms of Categorical Statements:
d u
A: All S is P (all students are people)
d d
E: No S is P (no students are pelicans)
u u
I: Some S is P (some students are Polish)
u d
O: Some S is not P (some students are not pilots)
Figures of Syllogisms:
1st Fig. 2nd Fig. 3rd Fig. 4th Fig.
M - P P - M M - P P - M
S - M S - M M - S M - S
S - P S - P S - P S - P
Five Rules of Validity
1. One distributed middle term: middle term must
be distributed in at least one premise.
2. Distributed term-distributed term: term is
distributed in conclusion iff it is distributed in
premise.
3. One affirmative premise: must have at least one
affirmative premise.
4. Negative-negative: negative conclusion iff
negative premise.
5. Particular-particular: cannot conclude a
particular from two universals.
PREDICATE LOGIC RULES
A: all S is P (all students are people)
∀x(Sx → Px)
E: no S is P (no student is a pelican)
∀x(Sx → ~Px)
I: some S is P (some students are pilots)
Ǝx(Sx & Px)
O: some S is not P (some students are not partiers)
Ǝx(Sx & ~Px)
QUANTIFICATION RULES
Universal Elimination/Instantiation (∀E, UI). Two
forms, works with both variables and constants.
∀x(Fx) / ˫ Fy
∀x(Fx) / ˫ Fa
Universal Introduction/Generalization (∀I, UG). One
form, works only with variables, not constants
(e.g., Fa / ˫ ∀x(Fx)).
Fy / ˫ ∀x(Fx)
Existential Introduction/Generalization (ƎI, EG). Two
forms, works with both variables and constants.
Fa / ˫ Ǝx(Fx)
Fy / ˫ Ǝx(Fx)
Existential Elimination/Instantiation (ƎE, EI). One
form, works only with constants, not variables
(e.g., Ǝx(Fx) / ˫ Fy). Also, existential name “a”
must be a new name that has not occurred in any
previous line.
Ǝx(Fx) / ˫ Fa
Quantifier Equivalence Rules (Quantifier Exchange
QE)
∀x(Fx) :: ~Ǝx~(Fx)
~∀x(Fx) :: Ǝx~(Fx)
∀x~(Fx) :: ~Ǝx(Fx)
~∀x~(Fx) :: Ǝx(Fx)
MODAL LOGIC: RULES
Modal operators
□p = it is necessary that p
◊p = it is possible that p
Truth assignment of □p and ◊p in possible worlds
Necessity: □p is true in world w1 if and only if p
is true in every world accessible to w1
Possibility: ◊p is true in world w1 if and only if
p is true in some world accessible to w1
Accessibility relations between possible worlds
Serial relation: every world has access to at least
one world
{w1}———→ {w2}
Reflexive relation: every world can access itself
{w1}
↻
Symmetric relation: for all worlds, w1, w2, if w1
has access to w2, then w2 has access to
w1
{w1} ←———→ {w2}
Transitive relation: For all worlds, w1, w2, w3,
if w1 has access to w2, and w2 has
access to w3, then w1 has access to w3
{w1} ———→ {w2} ———→ {w3}
⤷————————————⤴
Rules and Axioms
Necessitation Rule (NEC): if wff A is a proved
theorem (e.g., truth table tautology such
as “p v ~p”), then we may infer □A
Change Modal Operator Rule (CMO)
◊p :: ~□~p
□p :: ~◊~p
~□p :: ◊~p
□~p :: ~◊p
Major Axioms
AS1: ◊P ↔ ~□~P
AS2: □(P→Q) → (□P → □Q)
AS3: □P→ P
AS4: ◊P → □◊P