TFL: Truth-Functional Logic Flashcards
Associated conditional
The associated conditional of an inference is the single sentence in conditional form which has the conjunction of the premises as the antecedent and the conclusion as the consequent. e.g. ((p v q) & ¬p) → q
Disjunction
v: only true when at least one of p and q is true. inclusive: when either p or q or both are true. Exclusive: when either p or q are true, not both
Truth Table: P Q PVQ T T T T F T F T T F F F
conditional
p→q: p is the antecedent, q is the consequent. It means if p then q. not symmetric p→q is not q→p. if the antecedent is false the conditional is true - anything can be implied from a falsehood
Truth Table: p q p → q T T T T F F F T T F F T
biconditional
←→: iff, if and only if. p and q must have the same truth value
Truth Table: p q p ↔ q T T T T F F F T F F F T
contingent sentence
true on at least one line of the truth table and false on at least one line
Tautology
true on every line of the truth table
contradiction
false on every line of the truth table
necessary sentence
there is the same truth value on every line of the truth table. i.e tautology or contradiction
invalid argument
on at least one line of the truth table, the premises are true and the conclusion is false
truth-functional validity
- an inference in TFL is a valid form iff there is no assignment of truth values of its atomic components which makes the premises true and the conclusion false.
- if the set consisting of all the premises and the negated conclusion are truth-functionally inconsistent
the truth table method of ascertaining validity
- formalise the inference in TFL
- create a joint truth table for all the premises and the conclusion. The number of rows is 2^n where n is the number of atoms
- check to see if there is a line where the premises are true but the conclusion false.
- If there is no such case the inference is valid
semantics
truth values of atomic sentences
grammar rules in TFL
- every atomic sentence is a sentence
- if A is a sentence, ⌝A is a sentence
3-6. if A and B are sentences A&B, AvB, A→B, A←→B are sentences - Nothing else is a sentence
example of failure of TFL
- socrates is a person – p
- all people are mortal – q
- therefore, Socrates is mortal – .:r
This is valid in natural language but not in TFL
associated conditional method of testing for validity
- formulate the argument as an associated conditional. i.e. P1, P2, … Pn .: C becomes (P1 & P2 & … Pn) → C
- analyse this in a truth table
- the argument is valid iff the results demonstrate a tautology (i.e. result is true on every line).
HOT TIP: start with the consequent when doing the big ass truth tables
Reductio ad absurdum
take assumption, arrive at a contradiction, then reject the assumption and accept the negation of the assumption
the no counter example method of testing for validity
- formulate the argument in a truth table by putting each of the premises and the conclusion in their own column
- try every combination of truth-value assignments to the individual atomic sentences
- If you find a contradiction at any point, stop - the argument is valid
- if you do not find any inconsistencies the argument is invalid.
deductive system
a mechanical procedure you go through to test for (in)/validity
semantic trees method of testing for validity
- set the argument out as:
P1
P2
⌝C (i.e. negated conclusion)
in the centre of the page - use the semantic tree rules which demonstrate options at disjunctions, conditionals, biconditionals etc.
- close a branch (with *) if a contradiction arises
- if there are any remaining branches (i.e non-closed branches), the argument is invalid, if not the argument is valid
- remember to demonstrate the possibility of a counter-example when proving invalidity by reading off an interpretation that makes the premises all true and the negated conclusion also true.
HOT TIP: do straight down rules first
when is an argument a tautology, contradiction or contingent when using semantic trees?
- if all branches are closed the argument is a tautology because the negation of the argument is a contradiction. only in this case is the argument valid
- if branches are left open the argument is either a contradiction or a contingent argument
- to find out which one do the tree with an un-negated conclusion if (a) branches are still open then the argument is contingent because it is neither a tautology or a contradiction but if (b) branches close the argument is a contradiction
the union of set A and set B
AUB: the set of everything in either A or B or both
the intersection of set A and set B
A☊B:the set of everything in both A or B
consistency
a set of sentences is consistent iff it is possible for them all to be true together: in TFL this means there is are least one assignment of truth values to their atomic sentences that makes them all true together
how do you determine consistency
METHOD 1: Truth tables
- draw up a truth table with all of the sentences in different columns
- try out all the combinations of truth-value assignment to the elements until you find one that makes all the sentences true
- if you cannot find one the sentences are not consistent
METHOD 2: Semantic Trees
- set out the sentences in a tree (none are conclusions so do not negate any of them)
- use tree rules to derive contradictions and close branches where contradictions occur
- if the tree doesn’t close, the sentences are consistent, if the tree does close the sentences are inconsistent
theory
a set of sentences which is deductively closed if T.:S is valid s⍷T
Axioms
axioms imply everything else in the theory, axioms must be independent of each other e.g. Euclid’s Axioms which is meant to imply the entirety of geometry
independence
a sentence s of TFL is independent of a set A of sentences of TFL iff A.:s and A.:⌝s are both invalid. The sentence must be completely separate from all other sentences in the set
How do you test for independence?
use semantic trees: if s is independent of set A, the union of A with s/⌝s is consistent:
- set out the sentences in A as a semantic tree branch
- add the sentence you are testing
- follow through the semantic tree
- when contradictions occur, close the branch
- if all branches are closed, s is inconsistent with A. If this is the case s is not independent of A. Stop here.
- if branches are left open the sentence s is consistent with A (read off an example that demonstrates this)
- then restart the tree but this time use the negation of s instead of s
- if the tree is again consistent, read off an example and conclude that s is independent of A.
- if the tree is inconsistent, s is not independent of A
what logical properties are relevant to a sentence?
tautology, contradiction, contingent
what logical properties are relevant to arguments or inferences?
valid or invalid
what logical properties are relevant to sets of sentences or theories?
consistent or inconsistent
what logical properties are relevant to sets + a sentence?
independence / dependence
What is a function on a set?
a mapping that maps each of the object in that set to exactly one value
metalogical
about logic
functors
the expression in language which expresses a function - that function being out there in the world e.g. + is the functor of addition
when is a connective truth functional?
when the truth value of a sentence with that connective as main operator is uniquely determined by the truth values of the constituent sentences e.g & or → but not possibly p
what is truth functional equivalence (TFE)?
when a sentence in truth functional logic can be expressed in another way using different connectives e.g. p v q is equivalent to ⌝(⌝p&⌝q). the symbol for equivalence is: ≡
How do you prove TFE?
to prove sentence p is equivalent to sentence q:
- formulate two semantic trees with [p and q] and [p and ⌝q] respectively
- if both trees are valid (i.e. they close on all branches), then the sentences are TFE.
- this is because it proves that the arguments p.:q and q.:p are valid therefore equivalent in both directions .: equivalent
what is p v q equivalent to?
⌝(⌝p&⌝q)
what is p&q equivalent to?
⌝(⌝p v ⌝q)
what is p→q equivalent to?
⌝p v q
⌝(p&⌝q)
what is p←→q equivalent to?
(⌝pvq)&(⌝qvp)
⌝(p&⌝q)&⌝(q&⌝p)
what is the fewest number of connectives you could use to express the entirety of TFL
1: joint denial, alternative denial
joint denial
↓ NOR / negated OR
⌝p ≡ p↓p
pvq ≡ (p↓q)↓(p↓q)
Truth table: P Q P|Q T T F T F F F T F F F T
alternative denial
⎮ NAND / not and / scheffer stroke
⌝p ≡ p⎮p
pvq ≡ (p⎮p)⎮(q⎮q)
Truth table: A B A⎮B T T F T F T F T T F F T
what are always equivalent to one another:
a) contradictions
b) contingents
c) tautologies?
tautologies and contradictions
adequacy
a set of connectives s is adequate iff any truth function can be expressed by a TFL sentence whose only connectives are amongst s.
Disjunctive Normal Form (DNF)
A sentence of TFL is in DNF iff:
- No connectives occur other than ‘⌝’, ‘v’ or ‘&’
- Every occurrence of ‘⌝’ has minimal scope (i.e.⌝p but not ⌝(p&q))
- no ‘v’ occurs within the scope of any ‘&’ (i.e. you can’t have a&(bvc))
where ±A is an atomic sentence or it’s negation
(±A, &….& ±Ai) v (±Ai+1 &…& ±Ai) v (±An+1 &…& ±An)
Examples: a, (a&b) v (c&d), a v (c&⌝d&e) v ⌝b
DNF theorem
for any sentence of TFL, there is an equivalent sentence in DNF. Therefore all truth tables can be expressed in DNF where lines with true outcomes are shaped in DNF where true atoms as ‘A’ and not true atoms as ‘⌝A’. Lines with false outcomes are not included.
- Pick an arbitrary sentence s
- Let P1…Pn be the atomic sentences in s
- consider S’s truth table:
P1 P2 … Pn S
T T T T T/Fi
: : : : :
F F F F T/F2^n
- There are two cases to consider:
(a) S is false on every line of the truth table - it is a contradiction - if this is the case it is equivalent to all other contradictions .: S≡p&¬p
(b) S is true on at least one line of the truth table. for each line i of the truth table, let Ci be a conjunction of the form (±P1 & ±P2 &… & ±Pn.) Pi is negated when Pm is false on line i and not negated iff Pm is true on line i. Each Ci is true on and only on line i. - Let the number of lines on which S is true be a, b,… , n. Now let D be the sentence Ca v Cb v … v Cn. By construction D is in DNF and D≡S
How many lines in a truth table
2^n
