For this problem, the domain is the set of Northeastern students. Consider the following two predicates...

Transcribed Image Text:

For this problem, the domain is the set of Northeastern students. Consider the following two predicates Charlie(r) meaning Charlie knowsz P CS(z) meaning "z is a CS student " Using only variables, logic symbols (selected from V,A,,,3,V), and the predicates Char- lie() and CS(), formulate the statements: i. Charlie doesn't know every CS student. ii. The only students known to Charlie are CS students. iii. Charlie knows at least two students. Here you may also use symbols "=" and "", in addition to those listed above. iv. Charlie knows at most two students. Here again, you may use symbols "=" and "". 3 A formula is satisfiable if there exists some variable assignment that makes it true; that is, there is some row in its truth table that comes out to true instead of false. Determining whether an arbitrary boolean formula is satisfiable is called the satisfiability problem. There is no known efficient solution to this problem, in fact, an efficient solution would earn you a million dollar prize. While this is hard problem in computer science, not all instances of the problem are hard, in fact, determining satisfiability for some types of boolean formulae is easy. i. First, let's consider why this would be hard. If you knew nothing about a given boolean formula other than that it had n variables, how large is the truth table you would need to construct? Please indicate the number of columns and rows as a function of n (e.g n², n-1, etc) ii. Now consider the following 100 variable formula: (V₂) (₂ V 23) A... A (-299 V 100) Without constructing a truth table, how many satisfying assignments does this formula have? Explain your answer. For this problem, the domain is the set of Northeastern students. Consider the following two predicates Charlie(r) meaning Charlie knowsz P CS(z) meaning "z is a CS student " Using only variables, logic symbols (selected from V,A,,,3,V), and the predicates Char- lie() and CS(), formulate the statements: i. Charlie doesn't know every CS student. ii. The only students known to Charlie are CS students. iii. Charlie knows at least two students. Here you may also use symbols "=" and "", in addition to those listed above. iv. Charlie knows at most two students. Here again, you may use symbols "=" and "". 3 A formula is satisfiable if there exists some variable assignment that makes it true; that is, there is some row in its truth table that comes out to true instead of false. Determining whether an arbitrary boolean formula is satisfiable is called the satisfiability problem. There is no known efficient solution to this problem, in fact, an efficient solution would earn you a million dollar prize. While this is hard problem in computer science, not all instances of the problem are hard, in fact, determining satisfiability for some types of boolean formulae is easy. i. First, let's consider why this would be hard. If you knew nothing about a given boolean formula other than that it had n variables, how large is the truth table you would need to construct? Please indicate the number of columns and rows as a function of n (e.g n², n-1, etc) ii. Now consider the following 100 variable formula: (V₂) (₂ V 23) A... A (-299 V 100) Without constructing a truth table, how many satisfying assignments does this formula have? Explain your answer.