Propositional logic Flashcards Preview

Logic > Propositional logic > Flashcards

Flashcards in Propositional logic Deck (26)
Loading flashcards...
1

define a PL-wff

(i) Every sentence letter is a PL-wff
(ii) if 𝜙, 𝜓 are wff then ¬𝜙, (𝜙→𝜓), (𝜙∨𝜓), (𝜙∧𝜓), and (𝜙↔︎𝜓) are also PL-wffs
(iii) only what can be shown to be PL-wffs using (i) and (ii) are PL-wffs

2

When is a formula valid?

When the formula is true for all possible interpretations

3

When is an argument valid?

When the premises cannot be true and the conclusion false.

4

What is an informal proof?

A proof conducted in the natural language

5

What is a direct proof?

A proof that goes directly from the interpretations

6

What is an indirect proof?

A proof by contradiction that begins by assuming the contrary. (reductio ad absurdum).

7

When are two equations 𝜙 and 𝜓 semantically equivalent?

for all interpretations V(𝜙)=V(𝜓)

8

What is the natural deduction system?

The proof system that uses those long lines.

9

what does it mean to say that a language of propositional logic is "expressively adequate"?

it can express all truth-functions

10

Define completeness

A proof system is complete iff any valid formula and argument are provable in that system.

11

define logical consequence

certain claims logically follow from others - if the premises are true, then the conclusion is true

12

True or False:
A logically valid proposition is called a logical consequence

FALSE
a logically valid proposition is called a logical truth, a logically valid argument is called a logical consequence

13

define meta-language

The language used to describe the object language

14

what is a REFLEXIVE relation?

a has that relation to itself

15

what is a SYMMETRIC relation?

if a has R to b, then b has R to a

16

what is an ASYMMETRIC relation?

there is no a,b such that if a has R to b, then b has R to a

17

what is an ANTISYMMETRIC relation?

there is no distinct a,b such that if a has R to b, then b has R to a e.g. the identity relation

18

what is a TRANSITIVE relation?

if a has R to b, and b has R to c, then a has R to c

19

What is a unary connective?

a connective that combines with one formula (i.e. ¬)

20

What is a binary connective?

A connective that combines with two formulas (e.g. →,↔︎,∨,∧)

21

What, in particular, does Propositional Logic express?

Truth-functional thoughts

22

True or false:
what can be proved in one proof system can be proved in any other proof system

TRUE

23

Explain what is meant by '𝜙 is provable from a set of formulas'

there is a derivation that starts with the assumptions of the set of formulas and ends with 𝜙

24

Define soundness

A proof system is complete iff everything that we can prove in the system is valid

25

Which is the minimal standard and which is the gold standard of 'Completeness' and 'soundness'?

Soundness is the minimal standard (makes no errors)
completeness is the gold standard (has no gaps)

26

is natural deduction complete?

yes