Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

PH101: Logic > TFL: Truth-Functional Logic > Flashcards

TFL: Truth-Functional Logic Flashcards

1
Q

Associated conditional

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Disjunction

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

conditional

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

biconditional

A

←→: 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

contingent sentence

A

true on at least one line of the truth table and false on at least one line

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Tautology

A

true on every line of the truth table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

contradiction

A

false on every line of the truth table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

necessary sentence

A

there is the same truth value on every line of the truth table. i.e tautology or contradiction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

invalid argument

A

on at least one line of the truth table, the premises are true and the conclusion is false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

truth-functional validity

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

the truth table method of ascertaining validity

A
  1. formalise the inference in TFL
  2. 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
  3. check to see if there is a line where the premises are true but the conclusion false.
  4. If there is no such case the inference is valid
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

semantics

A

truth values of atomic sentences

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

grammar rules in TFL

A
  1. every atomic sentence is a sentence
  2. 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
  3. Nothing else is a sentence
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

example of failure of TFL

A
  1. socrates is a person – p
  2. all people are mortal – q
  3. therefore, Socrates is mortal – .:r
    This is valid in natural language but not in TFL
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

associated conditional method of testing for validity

A
  1. formulate the argument as an associated conditional. i.e. P1, P2, … Pn .: C becomes (P1 & P2 & … Pn) → C
  2. analyse this in a truth table
  3. 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Reductio ad absurdum

A

take assumption, arrive at a contradiction, then reject the assumption and accept the negation of the assumption

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

the no counter example method of testing for validity

A
  1. formulate the argument in a truth table by putting each of the premises and the conclusion in their own column
  2. try every combination of truth-value assignments to the individual atomic sentences
  3. If you find a contradiction at any point, stop - the argument is valid
  4. if you do not find any inconsistencies the argument is invalid.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

deductive system

A

a mechanical procedure you go through to test for (in)/validity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

semantic trees method of testing for validity

A
  1. set the argument out as:
    P1
    P2
    ⌝C (i.e. negated conclusion)
    in the centre of the page
  2. use the semantic tree rules which demonstrate options at disjunctions, conditionals, biconditionals etc.
  3. close a branch (with *) if a contradiction arises
  4. if there are any remaining branches (i.e non-closed branches), the argument is invalid, if not the argument is valid
  5. 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

when is an argument a tautology, contradiction or contingent when using semantic trees?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

the union of set A and set B

A

AUB: the set of everything in either A or B or both

22
Q

the intersection of set A and set B

A

A☊B:the set of everything in both A or B

23
Q

consistency

A

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

24
Q

how do you determine consistency

A

METHOD 1: Truth tables

  1. draw up a truth table with all of the sentences in different columns
  2. try out all the combinations of truth-value assignment to the elements until you find one that makes all the sentences true
  3. if you cannot find one the sentences are not consistent

METHOD 2: Semantic Trees

  1. set out the sentences in a tree (none are conclusions so do not negate any of them)
  2. use tree rules to derive contradictions and close branches where contradictions occur
  3. if the tree doesn’t close, the sentences are consistent, if the tree does close the sentences are inconsistent
25
Q

theory

A

a set of sentences which is deductively closed if T.:S is valid s⍷T

26
Q

Axioms

A

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

27
Q

independence

A

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

28
Q

How do you test for independence?

A

use semantic trees: if s is independent of set A, the union of A with s/⌝s is consistent:

  1. set out the sentences in A as a semantic tree branch
  2. add the sentence you are testing
  3. follow through the semantic tree
  4. when contradictions occur, close the branch
  5. if all branches are closed, s is inconsistent with A. If this is the case s is not independent of A. Stop here.
  6. if branches are left open the sentence s is consistent with A (read off an example that demonstrates this)
  7. then restart the tree but this time use the negation of s instead of s
  8. if the tree is again consistent, read off an example and conclude that s is independent of A.
  9. if the tree is inconsistent, s is not independent of A
29
Q

what logical properties are relevant to a sentence?

A

tautology, contradiction, contingent

30
Q

what logical properties are relevant to arguments or inferences?

A

valid or invalid

31
Q

what logical properties are relevant to sets of sentences or theories?

A

consistent or inconsistent

32
Q

what logical properties are relevant to sets + a sentence?

A

independence / dependence

33
Q

What is a function on a set?

A

a mapping that maps each of the object in that set to exactly one value

34
Q

metalogical

A

about logic

35
Q

functors

A

the expression in language which expresses a function - that function being out there in the world e.g. + is the functor of addition

36
Q

when is a connective truth functional?

A

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

37
Q

what is truth functional equivalence (TFE)?

A

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: ≡

38
Q

How do you prove TFE?

A

to prove sentence p is equivalent to sentence q:

  1. formulate two semantic trees with [p and q] and [p and ⌝q] respectively
  2. if both trees are valid (i.e. they close on all branches), then the sentences are TFE.
  3. this is because it proves that the arguments p.:q and q.:p are valid therefore equivalent in both directions .: equivalent
39
Q

what is p v q equivalent to?

A

⌝(⌝p&⌝q)

40
Q

what is p&q equivalent to?

A

⌝(⌝p v ⌝q)

41
Q

what is p→q equivalent to?

A

⌝p v q

⌝(p&⌝q)

42
Q

what is p←→q equivalent to?

A

(⌝pvq)&(⌝qvp)

⌝(p&⌝q)&⌝(q&⌝p)

43
Q

what is the fewest number of connectives you could use to express the entirety of TFL

A

1: joint denial, alternative denial

44
Q

joint denial

A

↓ 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
45
Q

alternative denial

A

⎮ 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
46
Q

what are always equivalent to one another:

a) contradictions
b) contingents
c) tautologies?

A

tautologies and contradictions

47
Q

adequacy

A

a set of connectives s is adequate iff any truth function can be expressed by a TFL sentence whose only connectives are amongst s.

48
Q

Disjunctive Normal Form (DNF)

A

A sentence of TFL is in DNF iff:

  1. No connectives occur other than ‘⌝’, ‘v’ or ‘&’
  2. Every occurrence of ‘⌝’ has minimal scope (i.e.⌝p but not ⌝(p&q))
  3. 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

49
Q

DNF theorem

A

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.

  1. Pick an arbitrary sentence s
  2. Let P1…Pn be the atomic sentences in s
  3. consider S’s truth table:

P1 P2 … Pn S
T T T T T/Fi
: : : : :
F F F F T/F2^n

  1. 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.
  2. 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
50
Q

How many lines in a truth table

A

2^n

PH101: Logic (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions