Scribd
Upload
12 views2 pages

Discrete Structures Test 1 - LAU Spring 2016

This document is a test for a Discrete Structure I course at the Lebanese American University, covering topics such as predicate logic, propositional logic, and proofs. It includes various problems related to logical formulas, resolution proofs, and Karnaugh maps. The test consists of multiple sections with specific tasks and points assigned to each question.

Uploaded by

nashimounir
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views2 pages

Discrete Structures Test 1 - LAU Spring 2016

This document is a test for a Discrete Structure I course at the Lebanese American University, covering topics such as predicate logic, propositional logic, and proofs. It includes various problems related to logical formulas, resolution proofs, and Karnaugh maps. The test consists of multiple sections with specific tasks and points assigned to each question.

Uploaded by

nashimounir
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Lebanese American University Spring 2016

Byblos

Discrete Structure I Date: 01/03/2016


Test #1 Duration: 1h 30

Name: ID:

1. (20 pts) Let ' be the following predicate logic formula:

¬[9x P (x, t) ! 8t Q(y, t)] _ [9z R(y, z) ^ S(z)]

(a) List free and bound occurrences of variables in '.


(b) Give the parse tree of '.
(c) Find the prenex form of '.

2. (30 pts) Assume that the following statements are true:


• Either the fridge is plugged in or I can see the milk.
• If the fridge door is open and the fridge is plugged in then the fridge light
is on.
• If the fridge light is o↵ then I cannot see the milk.
Consider the following propositional logic variables:
• A: The fridge is plugged in.
• B: I can see the milk.
• C: The fridge door is open.
• D: The fridge light is on.

(a) Write three propositional logic formulas that represent the three state-
ments above using A, B, C, D and logical connectives.
(b) We denote by the set of the three formulas of the preceding question.
Prove using three di↵erent methods (by contradiction, formal proof and
resolution proof) that ` ' where ' is the statement: If the fridge door
is open then the fridge light is on.

3. (12 pts) Express the following in predicate logic:


(a) If someone can fix your car, then Ralph can.
(b) Cats and dogs are the only suitable pets.
!

1
4. (30 pts) Find a resolution and a formal proof for the following:
(a) {a _ b ; s _ ¬a ; s _ ¬b} ` s
(b) ` (s ! (p ! ¬s)) ! (s ! ¬p)
(c) ` (¬p _ ¬q) ! ((p ! ¬q) ^ (q ! ¬p))

5. (18 pts) Find using Karnaugh maps a DNF and a CNF for the formula '
which has the following truth table:

p q r s φ

T T T T F

T T T F T

T T F T F

T F T T T

F T T T F

T T F F F

T F T F T

T F F T F

F F T T T

F T F T F

F T T F T

T F F F T

F T F F F

F F T F T

F F F T F

F F F F T

You might also like