Discrete Structures

You must justify your answers. The answers should be concise, clear and neat. When presenting proofs, every step should be justified.

Question 6: In this exercise, we will denote Boolean variables by lowercase letters, such as p and q. A proposition is any Boolean formula that can be obtained by applying the following recursive rules 1. For every Boolean variable p, p is a proposition 2. If f is a proposition, then-f is also a proposition 3. If f and g are propositions, then (f Vg) is also a proposition 4. If f and g are propositions, then (f A g) is also a proposition Let p and q be Boolean variables. Prove that is a proposition . Let denote the not-and operator. In other words, if f and g are Boolean formulas then (f 1 g) is the Boolean formula that has the following truth table (0 stands for false, and 1 stands for true): 0 - Let p be a Boolean variable. Use a truth table to prove that the Boolean formulas (pt p) and are equivalent Let p and q be Boolean variables. Use a truth table to prove that the Boolean formulas ((p p) (q q)) and pv q are equivalent Let p and q be Boolean variables. Express the Boolean formula (p^q) as an equivalent Boolean formula that only uses the -operator. Use a truth table to justify your answer Prove that any proposition can be written as an equivalent Boolean formula that only uses the t-operator