LOGIC Flashcards
What is the purpose of logic?
Purpose of logic is to deduce the validity of a statement from a set of premises.
What is propositional logic?
Statements can only be either true or false
e.g. “I have a pen” you can either have a pen or not
What is compound propositional logic?
Use of logical connectives to join different atomic propositions.
e.g. “we’re in paris” or “we’re in Berlin”
“we’re not in paris” (negation)
How can we denote different propositions?
Using single letters
e.g. F is “Today is Friday” and H is “I’m happy” then
not F is “Today is not friday”
What is negation?
¬ (not)
- 2 outcomes
Using negation, how to calculate when “I am not cold” equate to true?
- P = “I am cold”
- Check whether P is true
- Use truth table for negation
What is conjunction?
∧
(and)
Using conjunction, how to show “It is snowing and I am cold”?
- Set atomic propositions as letters P = It is snowing Q = I am cold
- Individually check P and Q
- Truth table for conjunction
What is disjunction?
∨
(or)
.. same question solve as add
What is implication?
⇒
(implies)
(if …… then ……)
How does implication truth table work?
For propositions P and L, P implies L if;
- If P = true, assumption is not held so it does not matter what conclusion is. So proves P ⇒ L
- if L = true , conclusion is already met, no matter what the assumption. So proves P ⇒ L
- if P = true and L = false. the assumption is held but the conclusion is not so P ⇒ L is false.
What is double implication?
⇔
(iff - if and only if)
How does double implication work?
P ⇔ Q can be written as:
P ⇒ Q ∧ Q ⇒ P or
If P then Q AND if Q then P
case 1: both True =
if P = T and Q = T then P ⇒ Q = T
if Q = T and P = T then Q ⇒ P = T
T ^ T = T
case 2/3: T and F (both ways) =
if P = T and Q = F then P ⇒ Q = F (based on implication truth table
if Q = F and P = T then Q ⇒ P = T
(based on implication truth table
F ^ T = F
case 4: both F =
if P = F and Q = F then P ⇒ Q = T
if Q = F and P = F then Q ⇒ P = T
T ^ T = T
What is the purpose of the precedence hierarchy?
Brackets are used to resolve any ambiguity in arguments. Hierarchy helps reduce number of brackets.
e.g. P ^ Q v R = (P ^ Q) v R
P ⇔ Q ⇒ R is ambiguous (meaning can change depending on brackets)
What is the precedence hierarchy?
Tight bind: NOT
AND
OR
Loose bind: IMPLIES, IFF
What is logical equivalence?
P1 is logically equivalent to P2 iff they have identical truth values under all possible assignments of truth values.
This allows substitution.
What is commutativity?
P v Q ⇔ Q v P
P ^ Q ⇔ Q ^ P
What is associability?
(P v Q) v R ⇔ P v (Q v R)
(P ^ Q) ^ R ⇔ P ^ (Q ^ R)
What is distributivity?
P ^ (Q v R) ⇔ (P ^ Q) v (P ^ R)
P v (Q ^ R) ⇔ (P v Q) ^ (P v R)
What is double negation?
¬(¬P) ⇔ P
What is idempotence?
P ^ P ⇔ P
P v P ⇔ P
What is de morgan law?
¬(P ^ Q) ⇔ ¬P v ¬Q
¬(P v Q) ⇔ ¬P ^ ¬Q
What are the 2 propositional constants?
true and false
true is always T
false is always F
What is a tautology?
Proposition that is true for ALL possible combinations
e.g. P v ¬P and (P v ¬Q) v (¬P ^ Q)
what is a contradiction?
Proposition that is false for ALL possible combinations
e.g. false and P ^ ¬P
What is a Valid argument?
A valid argument is an argument which has a valid conclusion where both premises are valid.
What is an argument, premise and conclusion?
ARGUMENT = collection of propositions
PREMISES = all other propositions to meet conclusion. Last column of truth table
CONCLUSION= proposition justified by the premises
How to check for a valid argument?
For every instance of each atomic proposition, a premise is found to be T or F.
If both premises are T, consider the conclusion.
Valid argument if final conclusion is also T
Invalid argument if final conclusion is F
