Flashcards in Definitions Deck (31)

Loading flashcards...

1

## What is a proportional formula?

###
1. Any propositional atom is a formula.

2. T and falsity are formulas.

3. If A is a formula, so is ~A

4. If A, B are formulas, all boolean connective forms are also.

2

## What is a literal?

###
A formula that's either atomic or negated atomic

3

## What is a clause?

### Disjunction ( v ) of one or more literals

4

## What is a situation?

###
Something that determines whether each propositional atom is true or false. It tells us the truth values of atoms.

For if-tests, a situation is some point in a program execution and thus the values of program variables at this point determine whether or not each atomic statement is true. (i.e the truth values of the propositional atoms)

5

## What is a valid argument in propositional logic?

###
Given formulas A1...An, B an argument:

A1...An, therefore B

is valid if B is true in every situation in which A1....An are all true.

If so, we use double turnstile to say that A1....An logically entails B.

6

## Alternative explanation of validity for propositional logic.

###
An argument is VALID if and only if it is impossible for all of the premises to be true and the conclusion to be false.

There can be a situation in which the premises are false and the conclusion is true.

7

## Valid, satisfiable and equivalent formulas

###
Valid formula: A propositional formula is valid if it is true in every situation. - often called tautologies.

Satisfiable formula: A propositional formula is satisfiable if it is true in at least one situation.

Equivalent formulas: Two propositional formulas A and B are logically equivalent if they are true in exactly the same situations.

8

## DNF and CNF

###
Disjunctive normal form:

Disjunction of conjunctions of literals and not further simplifiable without leaving this form.

Conjunctive normal form:

Conjunction of disjunction of literals (conjunction of clauses) and not further simplifiable without leaving this form.

9

## What is a theorem?

###
A formula that can be established ('proved') by a given proof system.

In ND, a theorem is any formula A such that (single turnstile) A holds.

10

## When is a proof system sound and complete?

###
A proof system is sound if every theorem is valid. (i.e every provable propositional formula is valid)

Therefore ND never makes mistakes.

A proof system is complete if every valid formula is a theorem.

(i.e every propositional validity can be proved)

ND is powerful enough to prove all valid formulas.`

11

## Soundness of ND

###
Soundness: If A1 ... An (single turnstile) B then A1 ... An (double turnstile) B

Any provable propositional formula is valid.

Natural deduction never makes mistakes.

12

## Completeness of ND

###
Completeness:

If A1 ... An (double turnstile) B then A1 ... An (single turnstile) B.

Any propositional validity can be proved.

Natural deduction is powerful enough to prove all valid formulas.

13

## What is consistency?

###
A formula A is consistent if (not single turnstile) ~A.

In other words, a consistent formula is one whose negation cannot be proved. Does not contain a contradiction.

A formula is consistent if and only if it is satisfiable since

14

## What is a signature?

###
A collection (set) of constants and relation symbols and function symbols with specified arities.

Replaces the collection of propositional atoms we had in propositional logic.

15

## What is an L-Term

###
For a signature L,

1. Any constant in L is an L-term.

2. Any variable is an L-term.

3. If f is an n-ary function symbol in L and t1...tn are L-terms then f(t1...tn) is an L-term.

4. Nothing else.

16

## What is a closed term/ground term?

### A term that doesn't involve a variable (i.e a constant)

17

## What is a first-order formula?

###
1. n-ary relation symbol R in L and t1 ... tn are L-terms. R(t1...tn) is an atomic L-formula.

2. If t and t' are L-terms then t = t' is an atomic L-formula.

3. Truth and falsity.

4. If A, B are L-formulas, so are all boolean connective combinations.

5. If A is an L-formula and x is a variable then A(x) and E(x).

6. Nothing else.

18

## What is a structure in predicate logic?

###
Situations in predicate logic.

Let L be a signature. An L-structure M is a thing that:

1. Identifies a non-empty collection of objects that M knows about. It's called the domain of M ( dom(M) )

2. Specifies what the symbols of L mean in terms of these objects.

Interpretation in M of a constant is an object in dom(M)

Interpretation in M of a relation symbol is a relation on dom(M)

19

## What is the meaning of a constant in a structure M?

###
The meaning of a constant c is the object c^M in structure M.

c^M is the interpretation of c in M (it's the object in dom(M) that c names in M)

20

## What is the effect of the A(x) [p -> q] in evaluating formulas with quantifiers in a structure?

###
Since p -> q will be true in the structure whenever p is false, we only need to check the objects in the structure such that p is true.

21

## Free and bound variables

###
Let A be a formula

Bound variable: If a variable lies under a quantifier A(x) or E(x) in the formation tree of A it is bound.

Free variable: If a variable does NOT lie under quantifiers in the formation tree of A then it is free.

22

## What is a sentence?

### A formula with no free variables.

23

## What is an assignment?

###
Since free variables have no meaning in a structure, we must supply them with a value using an assignment.

Let M be a structure. An assignment into M is something that allocates an object in dom(M) to each variable.

For an assignment h and a variable x, we write h(x) for the object assigned to x by h.

24

## What is the value of a term in an L-structure?

###
Let L be a signature, M an L-structure and h an assignment into M.

For any L-term t, the value of t in M under h is the object in M allocated to t by:

1. M, if t is a constant --- t^M

2. h, if t is a variable --- h(t)

3. If t is f(t1...tn) and the values of t1...tn are known to be a1...an then value of t is f^M(a1....an)

25

## At least two Suns

### A(x) E(y) [Sun(y) ^ y != x]

26

## At most one sun

###
1. Not (At least two suns)

2. A(x) A(y) [Sun(y) ^ Sun(x) -> y = x]

3. E(x) A(y) [Sun(y) -> y = x]

27

## Exactly one sun

###
1. At least one sun ^ at most one sun

2 E(x) A(y) [Sun(y) y = x]

28

## What is a function symbol in predicate logic?

### A function is a symbol that is interpreted in a structure as a function. In other words, for an n-ary function symbol f in L, an L-structure M must say which object in dom(M) f associates with each sequence (a1...an) of objects in dom(M).

29

## Validity in predicate logic

###
Let L be a signature and A1...An, B be L-formulas.

An argument 'A1....An, therefore B' is valid if for any L-structure M and assignment into H into M in which A1....An are all true, B must be true too.

30

## Soundness for predicate logic ND

###
Any provable first-order sentence is valid.

31