Writing a haskell function

Assignment Help Theory of Computation

Reference no: EM132979922

Question: Conjunctive normal form (CNF) is an adequate representation of Boolean functions, because every Boolean function can be written as a conjunction of disjunctions or literals. The set {∧, ∨, ¬} suffices to write all possible Boolean functions, that is, that set of connectives is functionally complete. In fact, from De Morgan's laws we can conclude that {∧, ¬} is a functionally complete set of connectives, since P ∨ Q ≡ ¬(¬P ∧ ¬Q), so that disjunction can always be translated into negation and conjunction. Similarly {∨, ¬} is functionally complete.

Task. Show that {⇒, f } is functionally complete. That is, show that every propositional formula has a logically equivalent formula that uses only variables, the "if-then" connective, and the constant f (denoting "false"). We ask you to do this by writing a Haskell function that turns an arbitrary propositional formula into an equivalent one that uses only ⇒ and f (plus any parentheses or propositional letters you need).

Reference no: EM132979922

Questions Cloud

Determine whether g is valid or not : Determine whether G is valid or not. Either provide a proof that uses resolution to show validity, or else specify an interpretation that makes G false

By how much share premium would increase on February : A corporation was organized in January 2016 with authorized capital of P10 par value ordinary shares. By how much share premium would increase on February

Implement haskell function to encode the logical constraints : Implement a Haskell function to encode the logical constraints implied by an equality logic formula's connectives as a formula in propositional logic

Design a circuit that is not minimal for a given function : Design such a circuit, using as few gates as possible. You can define any number of sub-circuits to help you reduce the gate count (simply give each a name)

Writing a haskell function : Writing a Haskell function that turns an arbitrary propositional formula into an equivalent one that uses only ? and f (plus any parentheses or propositional

Understanding of propositional logic : Understanding of propositional logic and first-order predicate logic, including their use in mechanised reasoning - Capture, as a single propositional formula

What is the asset turnover for the company : What is the Asset turnover for the company? Calculate the profit margin ratio of the company and comment on the profitability performance of the company.

COMP30026 Models of Computation Assignment : COMP30026 Models of Computation Assignment Help and Solution, University of Melbourne - Assessment Writing Service

What is the labor portion of the bid : A product has an average labor cost of $45/hr. If you include a 50% profit margin over your costs, what is the labor portion of the bid

User Account

All Pages