# Prposition logic | Computer Science homework help

The following quiz must be completed

** **

### Question 1

Not yet answered

Marked out of 100

Flag question

#### Question text

Which of these statements are true, for propositional logic? (In an exam you would have to justify your answers).

Select one or more:

A. If a formula is not satisfiable then it is not valid

B. X is not satisfiable if and only if ¬X is valid

C. If a formula is not valid then it is not satisfiable

D. X is not valid if and only if not X is satisfiable

### Question 2

Not yet answered

Marked out of 100

Flag question

#### Question text

For each propositional formula below, construct a truth table. Which formulas are valid?

Select one or more:

A.

B.

C.

D.

E.

### Question 3

Not yet answered

Marked out of 100

Flag question

#### Question text

In each case say if the formula is satisfiable.

Select one or more:

A.

B.

C.

D.

E.

### Question 4

Not yet answered

Marked out of 100

Flag question

#### Question text

Which of the following sets of connectives are functionally complete for propositional logic?

Select one or more:

A.

B. (false)

C.

D.

E.

### Question 5

Not yet answered

Marked out of 100

Flag question

#### Question text

Which of the following are propositional formulas, according to the strict definition of propositional formulas?

Select one or more:

A.

B.

C.

D.

E.

### Question 6

Not yet answered

Marked out of 100

Flag question

#### Question text

Consider the following 11 propositional formulas

Which of these eleven formulas are equivalent to each other. Choose one from the following:

Select one:

A. 1=5, 2=3, 7=11, 4=10, 6=9

B. None of the other answers are right

C. 1=5, 2=6, 3=9, 7=11

D. 1=5, 2=6, 4=7=10, 3=9

E. None are equivalent

### Question 7

Not yet answered

Marked out of 100

Flag question

#### Question text

Which of the following propositional formulas are in disjunctive normal form?

Select one or more:

A.

B.

C.

D.

E.

### Question 8

Not yet answered

Marked out of 100

Flag question

#### Question text

Which of the following statements is true?

Select one or more:

A. There is a DNF formula which is equivalent to all possible propositional formulas.

B. There is no DNF formula equivalent to

C. For every propositional formula there is a CNF formula equivalent to it.

D. For every propositional formula there is a DNF formula equivalent to it.

### Question 9

Not yet answered

Marked out of 100

Flag question

#### Question text

Let i be the propositional valuation where i(p) = t, i(q) = t, i(r) = f, …

Let v be the truth function that extends i. Which of the formulas below evaluate to true under this valuation v?

Select one or more:

A.

B.

C.

D.

### Question 10

Not yet answered

Marked out of 100

Flag question

#### Question text

Let L be a first order language with just one predicate, =, and no constants or function symbols. Let An be a sentence that is true in a structure M if and only if M has at least n points in its domain. What is the smallet number of variables required to write such a sentence An?

Select one:

A. 2

B. n

C. n-1

D. 1

E. infinity

### Question 11

Not yet answered

Marked out of 100

Flag question

#### Question text

Let where is the set of all where is strictly less than , constants denote zero and one respectively. Which of the following first order formulas are true in the structure S?

Select one or more:

A.

B.

C.

D.

E.

### Question 12

Not yet answered

Marked out of 100

Flag question

#### Question text

Let S be the structure where the domain is the set of natural numbers and I(<) is the set of pairs (x, y) where x is strictly less than y. Using S and the assignments A1 to A5 below, say which of the following are true.

A1:

x -> 7

y -> 14

z -> 9

w -> 5 (all other vars w)

** **

A2:

x -> 8

y -> 7

z -> 9

w -> 5 (all other w)

** **

A3:

x -> 0

y -> 14

z -> 9

w -> 5 (all other w)

** **

A4:

x -> 8

y -> 14

z -> 9

w -> 5 (all other w)

** **

A5:

x -> 6

y -> 14

z -> 9

w -> 5 (all other w)

Select one or more:

A. S, A1 |=

B. S, A1 |=

C. S, A3 |=

D. S, A2 |=

E. S, A2 |=

### Question 13

Not yet answered

Marked out of 100

Flag question

#### Question text

Let L be a first-order language with just = as a predicate and no constants or function symbols. How many variables to you need to express a sentence that is true in a model if and only if the domain has exactly n elements?

Select one:

A. 2

B. n+1

C. n

D. n-1

E. 2n+1

### Question 14

Not yet answered

Marked out of 100

Flag question

#### Question text

In the following formula > means greater than, = means equals, * means times. Which statement below is a good translation of the first order formula?

Select one:

A. for every composite number there is a prime number

B. for every prime number there is a bigger prime number

C. x and w are prime numbers

D. all numbers bigger than x are prime.

E. for all x, if x is a prime number then w is a prime number.

### Question 15

Not yet answered

Marked out of 100

Flag question

#### Question text

Consider the first order formula:

Which statements are correct?

Select one or more:

A. The scope of is

B. the scope of is

C. is in the scope of and , but not in .

D. there is one free occurence of : the in

E. This is not a well-formed formula.

### Question 16

Not yet answered

Marked out of 100

Flag question

#### Question text

Take a first order language with constants , predicates and functions .

Which of the following are terms in this language?

Select one or more:

A.

B.

C.

D.

E.

### Question 17

Not yet answered

Marked out of 100

Flag question

#### Question text

Let S be the structure where I(<) is the set of pairs (x, y) where x is strictly less than y.Which of these first order formulas are valid in S?

Select one or more:

A.

B.

C.

D.

E.

### Question 18

Not yet answered

Marked out of 100

Flag question

#### Question text

Which of these first order formulas are valid?

Select one or more:

A.

B.

C.

D.

### Question 19

Flag question

#### Question text

Predicate Logic. Consider the following assignments.

A1:

x -> 7

y -> 14

z -> 9

w -> 5 (all other vars w)

** **

A2:

x -> 8

y -> 7

z -> 9

w -> 5 (all other w)

** **

A3:

x -> 0

y -> 14

z -> 9

w -> 5 (all other w)

** **

A4:

x -> 8

y -> 14

z -> 9

w -> 5 (all other w)

** **

A5:

x -> 6

y -> 14

z -> 9

w -> 5 (all other w)

** **

Which statements are correct?

Select one or more:

A. A1 is an x-variant of A3

B. A5 is a z-variant of A5

C. A4 is a z-variant of A5

D. A2 is a y-variant of A4

E. A3 is an x-variant of A5

### Question 20

** **

#### Question text

Let S be the structure where I(<) is the set of pairs (x, y) where x is strictly less than y, I(+) is the ordinary addition function, I(0), I(1) are the integers zero, one respectively..Using the structure S calculate the interpretation of

+2(+2(1,1), +2(0,1))

Answer:

### Question 21

Let S be the structure where I(<) is the set of pairs (x, y) where x is strictly less than y. Let A be the assignment where x -> 5 and y -> 8.

Calculate [+ 2(x, y)]S,A

Answer: