Objective

• Explore multiple methods to determine satisfiability and logical equivalence of statements.
• Use Truth Tables and LogiSim to demonstrate whether statements are satisfiable.
• Use Truth Tables and LogiSim to demonstrate whether statements are equivalent.

Instructions

Install LogiSim. http://sourceforge.net/projects/circuit/

Answers to FAQ for Project 2:

Some explanations about circuits can be found on Chapter 10 of the textbook, as well as the definition of Satisfiability.

Questions 1, 2, and 3 require complete truth tables or equivalences. Check the directions carefully. This is all the stuff we learned in chapter 1

For questions 4, 5 and 6 you need to create logic circuits for each of the statements provided for those questions. The statements for questions 1 and 2 do not need circuits, and, actually, the examples provided in a file on FSO are the circuits for the statements on questions 3 and 4. Check them carefully, as they show many things you need for questions 4-6: They use AND, OR, NOT gates, they use initial and final pins, the circuits are as organized as possible. For the statements provided, DO NOT CHANGE ANYTHING. People tend to change one of the statements because they find ways to simplify. Even though some statements can be simplified, do not change them. Changing them will lower your grade.

You are not required to work in groups (but it is strongly suggested if you are not finding this course too easy). If you work in groups, please acknowledge who you worked with

Truth Tables

1.Let A: (PQ)(PQ)(PQ). Follow the steps below. (Download Example Circuit 1 for reference)

1.1. Create a Truth Table for A and include it in your document. Include columns forthe three clauses that comprise A along with A

1.2. Answer the following questions and include your answers in your document: Is A satisfiable? How did you determine this?

1.3. Answer the following and include your answers in your document: If A is satisfiable, then provide truth values that satisfy the statement. If not, then explain why it is not.

.

2.Let B:P(QR) C:(PQ)(PR). Follow the steps below.

2.1. Create a Truth Table for B, C and include it in your document. Include columns for the clauses that comprise B and C.

2.2. Answer the following questions and include your answers in your document: Are B and C equivalent? If not, then provide the truth values for which they differ.

Logical Arguments

3.Let D:(PQ)R E:(PR)(QR).

3.1. Formulate a logical argument whether D and E are equivalent in your document.

Circuit Design (Logisim)

4.Let A: (PQR)(PQS)(PQS)(PRS)(PQR)(PRS).

Rename the main circuit Satisfiability Test. Use the text tool to add your full name and the date..

Build the combinational circuit that represents A.

Is A satisfiable? If so, then provide the truth values that satisfy the statement. If not, explain why it is not. PLACE THIS ANSWER IN YOUR DOC

5.Let B:(PQR)(PQR)(PQR), C:((PQR)(PQR)(PQR)) Note the negation surrounding C.

Create a new circuit. Name this circuit Equivalence Test 1. Use the text tool to add your full name and the date.

Build the combinational circuits that represent each of B and C. (Be sure to present them exactly as they are stated above. Do not simplify/ apply DeMorgans Law beforehand.)

Are B and C equivalent? If not, give a set of truth values for which they differ. PLACE THIS ANSWER IN YOUR DOC

6.Let D: (PQRST)(PQRST)(PQRST)(PQRST)(PQRST), E: ((PQRST)(PQRST)(PQRST)(PQRST)(PQRST)) Note the outermost negation in E.

Create a new circuit. Name this circuit Equivalence Test 2. Use the text tool to add your full name and the date.

Build the combinational circuits that represent each of D and E. (Be sure to present them exactly as they are stated above. Do not simplify/ apply DeMorgans Law beforehand.)

Are D and E equivalent? If not, give a set of truth values for which they differ. PLACE THIS ANSWER IN YOUR DOC