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