Binary Connectives 17

Show that there are no complete single binary connectives other than NAND and NOR. Hint: Let f be the truth function for a complete binary connective. Show that f(true,true)=false and f(false,false)=true because the negation operation must be represented in terms of f. Then consider the remaining cases in the truth table for f.

Quadratic Residues

Please see the attached file for the fully formatted problems. Fix a positive integer a We say that a is a quadratic residue modulo n if there exists x such that a = x^2 mod n. (a) Let n be an odd prime and a be a non-zero quadratic residue modulo n. Show that there are exactly two values in{O.1....,n—1} satisfying x^2=amodn. (b) Show that if a is an odd prime, there are exactly (n + 1)/2 quadratic residues in {0, 1...., n — 1). (c) Give an example of positive integers a, n such that....

Show W is true for any interpretation whose domain has 2 elements.

Please see the attached file for the fully formatted problem. 71. 14b. Given the wff .... Show that W is true for any interpretation whose domain has two elements.

What is dual of each of the following Boolean expressions?

What is dual of each of the following Boolean expressions? 7b. x(y+z) 7d. xy+z

Making a Boolean algebra into a Partially Ordered Set

11b. A boolean algebra can be made into a partially ordered set by letting a≤b mean a=b. Show that a≤b iff b= a + b