comp2022 Assignment 1: Propositional Logic s2 2020
(a) Circuit 1 (b) Circuit 2 Figure 1: Circuits for Problems 2 and 3
Problem 3. Suppose we want to design a circuit with inputs p1, · · · , pn and outputs q1, · · · , qm. A specification of the input/output behaviour of a circuit can be given by a propositional formula S whose only atoms are p1,··· ,pn and q1,··· ,qm. We say that a circuit implements the specification S if C |= S where C is the propositional formula representing the circuit.
In the following, the only connectives you can use in the specifications are those introduced in the lecture slides.
a) Write a specification S1 of a circuit with three inputs a, b, c and one output z that says that at least one of the inputs is true and at least one of the inputs is false.
b) Write a specification S2 of a circuit with three inputs a, b, c and one output z that says z is true if and only if exactly two of the inputs (but it doesn’t matter which ones) are true.
c) True or False, and give a short reason: every circuit that implements S2 also implements S1.
d) Suppose a circuit is represented by the formula (z ↔((a ∨ b) ∧ ¬c)). Does this circuit implement the specification S1? Does it implement the specification S2? Give short reasons.
e) True or False, and give a short reason: every circuit that implements S1 also implements S2.
f) Draw a circuit that implements S2.
g) For each circuit in Figure 1, write a specification that is implemented by it (your specification should not be equivalent to ⊤, and the only atoms it should mention are the input/output atoms).
2
comp2022 Assignment 1: Propositional Logic s2 2020
Problem 4. Consider a circuit, let’s call it M, with 6 inputs a0, a1, b0, b1, b2, b3 and one output z. The circuit M behaves as follows: it outputs the value of bi where i = a0 +2a1. So, e.g., if a1 = 1,a0 = 0 then it outputs the value of the input variable b2.
a) What does M output on input a0 = 1, a1 = 1, b0 = 1, b1 = 1, b2 = 0, b3 = 1?
b) Write a specification S for the circuit M.
c) Suppose we introduce a new connective symbol to propositional logic for M. Let’s use the syntax (a0, a1 b0, b1, b2, b3). That is, the truth value of (a0, a1 b0, b1, b2, b3) under assignment α is defined to be α(bi) where i = a0 + 2a1.
In this question you will show how to express each of the connectives ∧, ∨, ¬, → only in terms of , ⊤, ⊥. That is:
1. Write a formula whose only connectives are , ⊤, ⊥ and that is logically equivalent to (p ∧ q).
2. Write a formula whose only connectives are , ⊤, ⊥ and that is logically equivalent to (p ∨ q).
3. Write a formula whose only connectives are , ⊤, ⊥ and that is logically equivalent to ¬p.
4. Write a formula whose only connectives are , ⊤, ⊥ and that is logically equivalent to (p → q).
You can typset in LaTeX by “\circledcirc” (this requires a package amssymb).
3