Foundations of Computer Science Equivalences to Transform Wff Into a CNF Questions

Description

I have 1 hour to complete this. I need the answers.

1 attachmentsSlide 1 of 1attachment_1attachment_1

Unformatted Attachment Preview

Foundations of Computer Science
1. Use equivalences to transform the following wff into a CNF:
(A  B)  ¬ D → C
2. Give a formal proof for the following tautology by using the CP rule:
C  (B → ¬ C)  (B  ¬ A) → ¬ A  D
3. Give a formal proof for the following tautology by using the IP rule:
(¬ A  ¬ D)  (C → A)  (B → D) → (¬ C  ¬ B)
4. Find a countermodel for the wff x(p(x) → q(x))  x¬ q(x) → x¬ p(x).
5. Find a model for the wff x y p(x, y)  x y ¬ p(x, y).
6. a) Determine L from the equation {^, b, baa}L = {^, aa, b, baa, baaaa}.
b) Find a grammar for the language {anbc 2n | n ≥ 0} = {b, abc2, a2bc 4, …, anbc 2n, …}.
7. Use the IP rule to prove that the following wff is valid:
x (p(x) → q(x))  ¬ x q(x) → ¬ x p(x)

Purchase answer to see full
attachment

Tags:
computer science

Formal Proof

tautology

CP rule

equivalences

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.