Translate in two ways each of these statements into

Suppose that the domain of the propositional function \(P(x)\) consists of \(-5,-3,-1,1,3\), and \(5 \). Express these statements without using quantifiers, instead using only negations, disjunctions, and conjunctions. a) \(\exists x P(x\) b) \(forall x P(x)\) c) \(\forall x((x \neq 1) \rightarrow P(x))\) d) \(\exists x((x \geq 0) \wedge P(x))\) e) \(\exists x(\neg P(x)) \wedge \forall x((x<0) \rightarrow P(x))\) Equation Transcription: Text Transcription: P(x) -5,-3,-1,1,3 exists xP(x) forall xP(x) forall x((x not equal 1) right arrow P(x)) exists x((x > or = 0)wedge P(x)) exists x(neg P(x))wedge forall x((x<0) right arrow P(x))

Problem 56E Given the Prolog facts in Example 28. What would Prolog return when given these queries? a) ?enrolled(kevin, ee222) ________________ b) ?enrolled(kiko, math273) ________________ c) ?instructor(grossman, X) ________________ d) ?instructor(X, cs301) ________________ e) ?teaches(X, kevin)

Problem 21E For each of these statements find a domain for which the statement is true and a domain for which the statement is false. a) Everyone is studying discrete mathematics. ________________ b)Everyone is older than 21 years. ________________ c) Every two people have the same mother. ________________ d) No two different people have the same grandmother.

Problem 1E Let P(x) denote the statement “x ? 4” What are these truth values? a) P(0) ________________ b) P(4) ________________ c) P(6)

Problem 2E Let P(x) be the statement “the word x contains the letter a.” What are these truth values? a) P(orange) ________________ b) P(lemon) ________________ c) P(true) ________________ d) P(false)

Problem 3E Let Q(x, y) denote the statement “x is the capital of y.” What are these truth values? a) Q(Denver, Colorado) ________________ b) Q(Detroit, Michigan) ________________ c) Q (Massachusetts, Boston) ________________ d) Q(New York, New York)

Translate these system specifications into English where the predicate \(S(x, y)\) is " \(x\) is in state \(y\) " and where the domain for \(x\) and \(y\) consists of all systems and all possible states, respectively. a) \(\exists x S(x\), open ) b) \(\forall x(S(x\) malfunctioning \() \vee S(x\), diagnostic)) c) \(\exists x S(x\) open) \(vee \exists x S(x\) diagnostic) d) \(\exists x \neg S(x\), available) e) \(\forall x \neg S(x\) working) Equation Transcription: Text Transcription: S(x,y) x y exists xS(x forall x(S(x vee S(x exists x neg S(x vee exists xS(x forall xS(x

Problem 40E Deal with the translation between system specification and logical expressions involving quantifiers. Express each of these system specifications using predicates, quantifiers, and logical connectives. a) When there is less than 30 megabytes free on the hard disk, a warning message is sent to all users. ________________ b)No directories in the file system can be opened and no files can be closed when system errors have been detected. ________________ c) The file system cannot be backed up if there is a user currently logged on. ________________ d)Video on demand can be delivered when there are at least 8 megabytes of memory available and the connection speed is at least 56 kilobits per second.

Translate these specifications into English where \(F(p)\) is "Printer \(p\) is out of service," \(B(p)\) is "Printer \(p\) is busy," \(L(j)\) is "Print job \(j\) is lost," and \(Q(j)\) is "Print job \(j\) is queued." a) \(\exists p(F(p) \wedge B(p)) \rightarrow \exists j L(j)\) b) \(\forall p B(p) \rightarrow \exists j Q(j)\) c) \(\exists j(Q(j) \wedge L(j)) \rightarrow \exists p F(p)\) d) \((\forall p B(p) \wedge \forall j Q(j)) \rightarrow \exists j L(j)\) Equation Transcription: Text Transcription: F(p) p B(p) L(j) Q(j) j exists p(F(p)?B(p)) right arrow exists jL(j) forall pB(p) right arrow exists jQ(j) exists j(Q(j)wedge L(j)) right arrow exists pF(p) (forall pB(p)wedge forall jQ(j)) right arrow exists jL(j)

Problem 57E Suppose that Prolog facts are used to define the predicates mother (M, Y) and father(F,X), which represent that M is the mother of Y and F is the father of X. respectively. Give a Prolog rule to define the predicate sibling(X. Y), which represents that X and Y are siblings (that is, have the same mother and the same father).

Problem 58E Suppose that Prolog facts are used to define the predicates mother (M, Y) and father (F, X), which represent that M is the mother of Y and F is the father of X, respectively. Give a Prolog rule to define the predicate grandfather(X, Y), which represents that X is the grandfather of Y. [Hint: You can write a disjunction in Prolog either by using a semicolon to separate predicates or by pulling these predicates on separate lines.]

Problem 4E State the value of x after the statement if P(x) then, x := 1 is executed, where P(x) is the statement “x > 1” if the value of x when this statement is reached is a) x = 0 ________________ b) x = 1 ________________ c) x = 2.

Problem 41E Deal with the translation between system specification and logical expressions involving quantifiers. Express each of these system specifications using predicates, quantifiers, and logical connectives. a) Al least one mail message, among the nonempty set of messages, can be saved if there is a disk with more than 10 kilobytes of free space. ________________ b) Whenever there is an active alert, all queued messages are transmitted. ________________ c) The diagnostic monitor tacks the status of all systems except the main console. ________________ d) Each participant on the conference call whom the host of the call did not put on a special list was billed.

Let \(N(x)\) be the statement " \(x\) has visited North Dakota," where the domain consists of the students in your school. Express each of these quantifications in English. a) \(\exists x N(x)\) b) \(\forall x N(x)\) c) \(\neg \exists x N(x)\) d) \(\exists x \neg N(x)\) e) \(\neg \forall x N(x)\) f) \(\forall x \neg N(x)\) Equation Transcription: Text Transcription: N(x) x \exists x N(x) \forall x N(x) \neg \exists x N(x) \exists x \neg N(x) \neg \forall x N(x) \forall x \neg N(x)

Problem 42E Deal with the translation between system specification and logical expressions involving quantifiers. Express each of these system specifications using predicates, quantifiers, and logical connectives. a) Every user has access to an electronic mailbox. ________________ b) The system mailbox can be accessed by everyone in the group if the file system is locked. ________________ c) The firewall is in a diagnostic state only if the proxy server is in a diagnostic state. ________________ d) At least one router is functioning normally if the throughput is between 100 kbps and 500 kbps and the proxy server is not in diagnostic mode.

Problem 5E Let P(x) be the statement “x spends more than five hours every weekday in class,” where the domain for x consists of all students. Express each of these quantifications in English.

Translate these statements into English, where \(C(x)\) is " \(x\) is a comedian" and \(F(x)\) is " \(x\) is funny" and the domain consists of all people. a) \(\forall x(C(x) \rightarrow F(x))\) b) \(\forall x(C(x) \wedge F(x))\) c) \(\exists x(C(x) \rightarrow F(x))\) d) \(\exists x(C(x) \wedge F(x))\) Equation Transcription: Text Transcription: C(x) x F(x) forall x(C(x) right arrow F(x)) forall x(C(x) wedge F(x)) exists x(C(x) right arrow F(x)) exists x(C(x)wedge F(x))

Translate these statements into English, where \(R(x)\) is " \(x\) is a rabbit" and \(H(x)\) is "\(x\) hops" and the domain consists of all animals. a) \(\forall x(R(x) \rightarrow H(x))\) b) \(\forall x(R(x) \wedge H(x))\) c) \(\exists x(R(x) \rightarrow H(x))\) d) \(\exists x(R(x) \wedge H(x))\) Equation Transcription: Text Transcription: R(x) x H(x) forall x(R(x) right arrow H(x)) forall x(R(x) wedge H(x)) exists x(R(x)right arrow H(x)) exists x(R(x) wedge H(x))

Problem 9E Let P(x) be the statement “x can speak Russian” and let Q(x) be the statement “x knows the computer language C++.” Express each of these sentences in terms of P(x), Q(x), quantifiers, and logical connectives. The domain for quantifiers consists of all students at your school. a) There is a student at your school who can speak Russian and who know s C++ ________________ b) There is a student at your school who can speak Russian but who doesn’t know C++. ________________ c) Every student at your school either can speak Russian or knows C++. ________________ d) No student at your school can speak Russian or knows C++.

Problem 44E Determine whether ?x(P(x) ? Q(x)) and ?x P(x) ? ?x Q(x) are logically equivalent. Justify your answer.

Problem 45E Show that ?x(P(x) v Q(x)) and ?x P(x) v ?x Q(x) are logically equivalent.

Problem 46E Establish rules for null quantification that we can use when a quantified variable does not appear in part of a statement. Establish these logical equivalences, where x does not occur as a free variable in A. Assume that the domain is nonempty. a) (?x P(x) ? A ? ?x(P(x) ? A) ________________ b) (?x P(x) ? A ? ?x(P(x) ? A)

Problem 11E Let P(x) be the statement “x= x2”. If the domain consists of the integers, what are these truth values?

Problem 10E Let C(x) be the statement “x has a cat,” let D(x) be the statement “x has a dog”, and let F(x) be the statement “x has a ferret”. Express each of these statements in terms of C(x), D(x), F(x), quantifiers, and logical connectives. Let the domain consist of all students in your class. a) A student in your class has a cat, a dog, and a ferret. ________________ b) All students in your class have a cat, a dog, or a ferret. ________________ c) Some student in your class has a cat and a ferret, but not a dog. ________________ d) No student in your class has a cat, a dog, and a ferret. ________________ e) For each of the three animals, cats, dogs, and ferrets, there is a student in your class who has this animal as a pet.

Problem 47E Establish rules for null quantification that we can use when a quantified variable does not appear in part of a statement. Establish these logical equivalences, where x does not occur as a free variable in A. Assume that the domain is nonempty. a)(?x P(x)) ?A ? ?x(P(x) ? A) ________________ b)(?x P(x)) ? A ? ?x(P(x) ?A)

Problem 12E Let Q(x) be the statement “x +1 > 2x.” If the domain consists of all integers, what are these truth values?

Problem 48E Establish rules for null quantification that we can use when a quantified variable does not appear in part of a statement. Establish these logical equivalences, where x does not occur as a free variable in A. Assume that the domain is nonempty. a) ?x(A ? P(x)) ? A ??x P(x) ________________ b) ?x(A ? P(x)) ? A ? ?x P(x)

Problem 49E Establish rules for null quantification that we can use when a quantified variable does not appear in part of a statement. Establish these logical equivalences, where x does not occur as a free variable in A. Assume that the domain is nonempty. a) ?x(P(x) ? A) ? ?x P(x) ? A ________________ b) ?x(P(x) ?A) ? ?x P(x) ? A

Problem 13E Determine the truth value of each of these statements If the domain consists of all integers.

Problem 14E Determine the truth value of each of these statements if the domain consists of all real numbers.

Problem 15E Determine the truth value of each of these statements if the domain for all variables consists of all integers.

Problem 51E Show that ?x P(x) ? ?x Q (x) and ?x (P(x) ? Q(x)) are not logically equivalent.

Problem 50E Show that ?x P(x)??x Q(x) and ?x (P(x) ? Q(x)) are not logically equivalent.

Problem 52E As mentioned in the text the notation ?!x P(x) denotes “There exists a unique x such that P(x) is true.” If the domain consists of all integers, what are the truth values of these statements?

Problem 16E Determine the truth value of each of these statements if the domain of each variable consists of all real numbers,

Problem 17E Suppose that the domain of the propositional function P(x) consists of the integers 0, 1, 2, 3, and 4. Write out each of these propositions using disjunctions, conjunctions, and negations.

Problem 18E Suppose that the domain of the propositional function P{x} consists of the integers -2, –1, 0, 1, and 2. Write out each of these propositions using disjunctions, conjunctions, and negations.

Problem 53E What are the truth values of these statements?

Problem 54E Write out ?!x P(x)¸where the domain consists of the integers 1, 2, and 3, in terms of negations, conjunctions, and disjunctions.

Problem 55E Given the Prolog facts in Example 28. what would Prolog return given these queries? a) instructor(chan, math273) ________________ b) ?instructor(patel, cs301) ________________ c) ?enrolled(X, cs301) ________________ d) ?enrolled(kiko, Y) ________________ e) ?teaches(grossman, Y)

Problem 19E Suppose that the domain of the prepositional function P(x) consists of the integers 1, 2, 3, 4, and 5. Express these statements without using quantifiers, instead using only negations, disjunctions, and conjunctions.

Problem 24E Translate in two ways each of these statements into logical expressions using predicates, quantifiers, and logical connectives. First, let the domain consist of the students in your class and second, let it consist of all people. a) Everyone in your class has a cellular phone. ________________ b)Somebody in your class has seen a foreign movie. ________________ c) There is a person in your class who cannot swim. ________________ d)All students in your class can solve quadratic equations. ________________ e) Some student in your class does not want to be rich.

Problem 22E For each of these statements find a domain for which the statement is true and a domain for which the statement is false. a) Everyone speaks Hindi. ________________ b) There is someone older than 21 years. ________________ c) Every two people have the same first name. ________________ d) Someone knows more than two other people.

Problem 23E Translate in two ways each of these statements into logical expressions using predicates, quantifiers, and logical connectives. First, let the domain consist of the students in your class and second, let it consist of all people. a)Someone in your class can speak Hindi. ________________ b)Everyone in your class is friendly. ________________ c)There is a person in your class who was not born in California. ________________ d)A student in your class has been in a movie. ________________ e) No student in your class has taken a course in logic programming.

Problem 59E Are based on questions found in the book Symbolic Logic by Lewis Carroll. Let P(x), Q(x), and R(x) be the statements “xis a professor,” “x is ignorant.” and “x is vain,” respectively. Express each of these statements using quantifiers; logical connectives; and P(x), Q(x), and R(x), where the domain consists of all people. a) No professors are ignorant. ________________ b) All ignorant people are vain. ________________ c) No professors are vain. ________________ d) Does (c) follow from (a) and (b)?

Problem 60E Are based on questions found in the book Symbolic Logic by Lewis Carroll. Let P(x), Q(x), and R(x) be the statements “x is a clear explanation,” “x is satisfactory.” and “x is an excuse.” respectively. Suppose that the domain for xconsists of all English text. Express each of these statements using quantifiers, logical connectives, and P(x), Q(x), and R(x). a) All clear explanations are satisfactory. ________________ b) Some excuses are unsatisfactory. ________________ c) Some excuses are not clear explanations. ________________ *d) Does (c) follow from (a) and (b)?

Problem 61E Are based on questions found in the book Symbolic Logic by Lewis Carroll. Let P(x), Q(x), R(x), and S(x) be the statements “x is a baby,” “x is logical.” “x is able to manage a crocodile,” and “xis despised,” respectively. Suppose that the domain consists of all people. Express each of these statements using quantifiers; logical connectives; and P (x), Q (x), R (x), and S(x). a) Babies are illogical. ________________ b) Nobody is despised who can manage a crocodile. ________________ c) Illogical persons are despised. ________________ d) Babies cannot manage crocodiles. ________________ *e) Does (d) follow from (a), (b), and (c)? If not, is there a corned conclusion?

Problem 25E Translate each of these statements into logical expressions using predicates, quantifiers, and logical connectives. a) No one is perfect. ________________ b)Not everyone is perfect. ________________ c) All your friends are perfect. ________________ d)At least one of your friends is perfect. ________________ e) Everyone is your friend and is perfect. ________________ f) Not everybody is your friend or someone is not perfect.

Problem 27E Translate each of these statements into logical expressions in three different ways by varying the domain and by using predicates with one and with two variables. a) A student in your school has lived in Vietnam. ________________ b) There is a student in your school who cannot speak Hindi. ________________ c) A student in your school knows Java, Prolog, and C++. ________________ d) Everyone in your class enjoys Thai food. ________________ e) Someone in your class does not play hockey.

Problem 28E Translate each of these statements into logical expressions using predicates, quantifiers, and logical connectives. a) Something is not in the correct place. ________________ b) All tools are in the correct place and are in excellent condition. ________________ c) Everything is in the correct place and in excellent condition. ________________ d) Nothing is in the correct place and is in excellent condition. ________________ e) One of your tools is not in the correct place, but it is in excellent condition.

Problem 62E Are based on questions found in the book Symbolic Logic by Lewis Carroll. Let P(x), Q(x), R(x), and S(x) be the statements “x is a duck,” “x is one of my poultry,” “x is an officer,” and “x is willing to waltz,” respectively. Express each of these statements using quantifiers; logical connectives; and P(x), Q(x), R(x), and S(x) a) No ducks are willing to waltz. ________________ b)No officers ever decline to waltz. ________________ c) All my poultry are ducks. ________________ d)My poultry are not officers. ________________ *e) Does (d) follow from (a), (b), and (c)? If not, is there a correct conclusion?

Problem 29E Express each of these statements using logical operators, predicates, and quantifiers. a) Some propositions are tautologies. ________________ b)The negation of a contradiction is a tautology. ________________ c) The disjunction of two contingencies can be a tautology. ________________ d) The conjunction of two tautologies is a tautology.

Suppose the domain of the propositional functionP \((x, y)\) consists of pairs \(x\) and \(y\), where \(x\) is 1 , 2 , or 3 and \(y\) is 1,2 , or 3 . Write out these propositions using disjunctions and conjunctions. a) \(\exists x P(x, 3)\) b) \(\forall y P(1, y)\) c) \(\exists y \neg P(2, y)\) d) \(\forall x \neg P(x, 2)\) Equation Transcription: Text Transcription: (x,y) \exists x P(x, 3) \forall y P(1, y) \exists y \neg P(2, y) \forall x \neg P(x, 2)

Suppose that the domain of \(Q(x, y, z)\) consists of triples \(x, y, z\), where \(x=0,1\), or \(2, y=0\) or 1 , and \(z=0\) or 1 . Write out these propositions using disjunctions and conjunctions. a) \(\forall y Q(0, y, 0)\) b) \(\exists x Q(x, 1,1)\) c) \(\exists z \neg Q(0,0, z)\) d) \(\exists x \neg Q(x, 0,1)\) Equation Transcription: , Text Transcription: Q(x,y,z) x,y,z x=0,1, 2,y=0 \forall y Q(0, y, 0) \exists x Q(x, 1,1) \exists z \neg Q(0,0, z) \exists x \neg Q(x, 0,1)

Problem 32E Express each of these statements using quantifiers. Then form the negation of the statement so that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase “It is not the case that.”) a) All dogs have fleas. ________________ b)There is a horse that can add. ________________ c) Every koala can climb. ________________ d)No monkey can speak French. ________________ e) There exists a pig that can swim and catch fish.

Problem 33E Express each of these statements using quantifiers. Then form the negation of the statement, so that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase “It is not the case that.”) a) Some old dogs can learn new tricks. ________________ b)No rabbit knows calculus. ________________ c) Every bird can fly. ________________ d)There is no dog that can talk. ________________ e) There is no one in this class who knows French and Russian.

Problem 34E Express the negation of these propositions using quantifiers, and then express the negation in English. a) Some drivers do not obey the speed limit. ________________ b)All Swedish movies are serious. ________________ c) No one can keep a secret. ________________ d) There is someone in this class who does not have a good attitude.

Find a counterexample, if possible, to these universally quantified statements, where the domain for all variables consists of all integers. a) \(\forall x\left(x^{2} \geq x\right)\) b) \(\forall x(x>0 \vee x<0)\) c) \(\forall x(x=1)\) ________________ Equation Transcription: Text Transcription: forall x(x^{2} \geq x) forall x(x>0 \vee x<0) forall x(x=1)

Problem 43E Determine whether ?x(P(x) ? Q(x)) and ?x P(x) ? ?x Q(x) are logically equivalent. Justify your answer.

Problem 37E Express each of these statements using predicates and quantifiers. a) A passenger on an airline qualifies as an elite flyer if the passenger flies more than 25,000 miles in a year or takes more than 25 flights during that year. ________________ b)A man qualifies for the marathon if his best previous time is less than 3 hours and a woman qualifies for the marathon if her best previous time is less than 3.5 hours. ________________ c) A student must lake at least 60 course hours, or at least 45 course hours and write a master’s thesis, and receive a grade no lower than a B in all required courses, to receive a master’s degree. ________________ d) There is a student who has taken more than 21 credit hours in a semester and received all A’s.

Find a counterexample, if possible, to these universally quantified statements, where the domain for all variables consists of all real numbers. a) \(\forall x\left(x^{2} \neq x\right)\) b) \(\forall x\left(x^{2} \neq 2\right)\) c) \(\forall x(|x|>0)\) Equation Transcription: Text Transcription: forall x(x^2 neq x) forall x(x^2 neq 2) forall x(|x|>0)