Test 1 Flashcards
¬
NOT, Negation, inverses value, T becomes F, F becomes T.
∧
AND, Conjunction, both have to be true.
∨
Inclusive OR, disjunction, if either is true the compound statement is true.
⊕
Exclusive OR (XOR), exclusive disjunction, only true if ONE statement true but not both.
↔
If and only if (IFF), biconditional, only true if both values the same, 2T or 2F.
→
Implies, conditional, only false if true implies false.
How to prove something is a WFF?
- Show individual atoms are WFF e.g p, q, r
- If the atoms are WFF so too are (¬p) (p∧q) etc.
- Keep expanding for the whole example.
What is De Morgan’s Law?
A way of pushing ¬ inside brackets.
e.g ¬(p∧q) becomes ¬p ∨ ¬q.
The ¬ goes in front of the atoms, AND switch to OR,
OR switches to AND.
What is double negation?
When there are 2 NOTs together so they cancel out.
eg ¬¬P ≡ P
≡
Logically equivalent, relationship between WFFs, not a logical connective
Tautology
All outputs true
Satisfiable
At least 1 output true.
Contradiction
All outputs false.
What logical connectives can generate all truth tables?
¬, ∧, V
Associativity
When you have the same connective (all ∧ or V) then you don’t need brackets because of associativity.
Commutativity
p∧q ≡ q∧p and pVq ≡ qVp
Idempotence
p∧p ≡ p and pVp ≡ p
Distributivity
p∧(q∨r) ≡ (p∧q)∨(p∧r) and p∨(q∧r) ≡ (p∨q)∧(p∨r)
Absorption
p ∨ (p ∧ q) ≡ p and p ∧ (p ∨ q) ≡ p
|=
Semantic turnstile. If on the left of a WFF it means it is a tautology, if on the right of a WFF means it is a Contradiction
How to show 2 WFF are logical equivalents?
WFF A ≡ WFF B if and only if |= A ↔ B (a tautology)
Contingency
A WFF that is sometimes true and sometimes false
What does Satisfy the WFF mean?
A truth assignment that makes a WFF true is said to satisfy the WFF.
What does falsify the WFF mean?
A truth assignment that makes a WFF false is said to falsify the WFF.
The Satisfiability Problem
(SAT) Given a wff in PL, decide whether there is some truth assignment to the atoms that make the wff take the value true. A program that solves SAT is called a SAT solver.
Statement
A Sentence that can be true or false.
Compound statement
Statements glued together with logical connectives so the T or F can be calculated.
How to figure out how many rows a truth table will have?
2^n where n is the number of atoms.
∴
Therefore
