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