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