程序代写代做代考 C comp2022 Assignment 1: Propositional Logic s2 2020

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