Question 1. 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. For each propositional formula below, construct a truth table. Which formulas are valid?

Select one or more:

A. (p\rightarrow p)

B. p

C. (p\wedge q)

D. ((p\rightarrow(q\vee r)) \leftrightarrow((p\rightarrow q)\vee(p\rightarrow r)))

E. (p\rightarrow(q\rightarrow p))

Question 3. In each case say if the formula is satisfiable.

Select one or more:

A. \neg(p\rightarrow(q\rightarrow p))

B. p

C. \neg((p\rightarrow q)\rightarrow p)

D. (p\wedge q)

E. (p\wedge\neg p)

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

Select one or more:

A. \wedge, \vee, \neg

B. \rightarrow, \bot (false)

C. \vee, \neg

D. \wedge, \vee

E. \rightarrow, \wedge

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

Select one or more:

A. \neg(p)

B. p\rightarrow q

C. (p\wedge q)

D. ((p\rightarrow q)\rightarrow p)

E. (p\wedge q\wedge r)

Question 6. Consider the following 11 propositional formulas

(p\rightarrow(q\rightarrow p))
(q \rightarrow p)
( \neg p \vee q )
(\neg p \wedge \neg q )
(p \vee \neg p )
(p \vee \neg q )
((p \vee\neg q) \wedge (\neg p \vee q))
(p \wedge\neg p)
(p \rightarrow q)
((p \wedge \neg q) \vee (\neg p \wedge q))
(p \leftrightarrow q)

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. Which of the following propositional formulas are in disjunctive normal form?

Select one or more:

A. \neg p

B. (p \vee\neg q)

C. ((p \vee\neg q) \wedge r)

D. ((p \wedge q) \vee (\neg p \wedge\neg q))

E. ((\neg p \wedge q) \vee (p \wedge \neg q))

Question 8. 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 (p \wedge\neg p)

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. 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. (((p \leftrightarrow q) \rightarrow\neg(p \wedge\neg r)) \vee\neg r )

B. (\neg p \rightarrow (q \wedge\neg p))

C. (p \wedge\neg r)

D. (\neg p \rightarrow q)

Question 10. 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. Let S=({\mathbb N}, I) where I(<^2) is the set of all (x, y) where x is strictly less than y, constants 0, 1 denote zero and one respectively. Which of the following first order formulas are true in the structure S?

Select one or more:

A. \forall x\exists y <^2(x, y)

B. \neg (<^2(0, 1)\rightarrow(0=+^2(0, 1)))

C. <^2(1, +^2(1, 0))

D. \forall x\exists y <^2(y, x)

E. (<^2(1, +^2(0, 0))\vee (1=+^2(0, 1)))

Question 12. Let S be the structure ({\mathbb N}, I) 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 |= \small \exists x <^2(x, 1)

B. S, A1 |= \small \forall x\exists y <^2(x, y)

C. S, A3 |= \small <^2(x, 1)

D. S, A2 |= \small <^2(x, 1)

E. S, A2 |= \small \neg\exists z(<^2(y, z)\wedge <^2(z, x))

Question 13.  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. In the following formula > means greater than, = means equals, * means times. Which statement below is a good translation of the first order formula?

\small \forall x[\neg(\exists y\exists z(x=y*z\wedge y>1\wedge z>1))\rightarrow\exists w(w>x\wedge\neg(\exists y\exists z(w=y*z\wedge y>1\wedge z>1)))]

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. Consider the first order formula:

\small (\forall x(\exists y P^2(x, y)\rightarrow R^2(y, x))\rightarrow Q^1(x))

Which statements are correct?

Select one or more:

A. The scope of \small \forall x is \small ((\exists y P^2(x, y)\rightarrow\exists x R^2(y, x))\rightarrow Q^1(x))

B. the scope of \small \exists y is \small P^2(x, y)

C. \small R^2(y, x) is in the scope of \small \exists x and \small \exists y, but not in \small \forall x.

D. there is one free occurence of \small x: the \small x in \small Q^1(x)

E. This is not a well-formed formula.

Question 16. Take a first order language with constants C = \{0,1\}, predicates P = \{R^2\} and functions F = \{+^2, -^1, \times^2\}.

Which of the following are terms in this language?

Select one or more:

A. +^2(x, y, 1)

B. \times^2(+^2(0, 1), +^2(0, 1))

C. R^2(x, 0)

D. -^1(0, 1)

E. +^2(3, 0)

Question 17. Let S be the structure ({\mathbb N}, I) 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. \exists x\forall y(<^2(x, y)\vee (x=y))

B. \forall y\exists x(<^2(x, y)\vee (x=y))

C. \forall x\forall y((<^2(x, y)\vee <^2(y, x))\vee x=y)

D. \forall y\exists x <^2(y, x)

E. \exists x\forall y <^2(y, x)

Question 18. Which of these first order formulas are valid?

Select one or more:

A. (\forall x\neg R^1(x) \rightarrow\neg\exists x R^1(x))

B. (\exists x\forall y <^2(x, y)\rightarrow \forall y\exists x <^2(x, y))

C. \forall x\forall y ((<^2(x, y)\vee <^2(y, x))\vee(x=y))

D. (\forall x\exists y <^2(x, y) \rightarrow \exists y\forall x <^2(x, y))

Question 19. 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. Let S be the structure ({\mathbb N}, I) 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))

Question 21. Let S be the structure ({\mathbb N}, I) 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