Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 2: Problem 3

Which of the following DNF formulas are satisfiable? If the formula is satisfiable, give an interpretation that satisfies it. If it is not satisfiable, explain why not. (a) \((a \wedge b \wedge c) \vee(c \wedge \neg c \wedge b)\) (b) \((a \wedge b \wedge c \wedge d \wedge \neg b) \vee(c \wedge d \wedge \neg c \wedge e \wedge f)\) (c) \((a \wedge b \wedge c) \vee(\neg a \wedge \neg b \wedge \neg c)\)

Short Answer

Expert verified
(a) Satisfiable: \(a = b = c = \text{true}\). (b) Not satisfiable. (c) Satisfiable: \(a = b = c = \text{true}\) or all false.

Step by step solution

01

Analyze Formula (a)

The formula is \((a \wedge b \wedge c) \vee(c \wedge eg c \wedge b)\). This is a disjunction of two clauses. The clause \(a \wedge b \wedge c\) involves three variables, and it is true if all variables are true. The clause \(c \wedge eg c \wedge b\) contains a contradiction because of \(c \wedge eg c\), making this part always false.
02

Determine Satisfiability of Formula (a)

Since \(c \wedge eg c\) is always false, we only need to check the clause \(a \wedge b \wedge c\). The formula is satisfiable because if you assign \(a = \text{true}, b = \text{true}, c = \text{true}\), the entire formula becomes true.
03

Analyze Formula (b)

The formula is \((a \wedge b \wedge c \wedge d \wedge eg b) \vee(c \wedge d \wedge eg c \wedge e \wedge f)\). Both sub-clauses contain contradictions: the first clause has \(b \wedge eg b\), and the second has \(c \wedge eg c\), making both clauses always false.
04

Determine Satisfiability of Formula (b)

Because both clauses contain contradictions and are always false, the entire formula is unsatisfiable. There are no assignments of truth values that can make it true.
05

Analyze Formula (c)

The formula is \((a \wedge b \wedge c) \vee(eg a \wedge eg b \wedge eg c)\). The first sub-clause is true when \(a, b,\) and \(c\) are all true. The second sub-clause is true when \(a, b,\) and \(c\) are all false. This means there are scenarios where either clause can be true.
06

Determine Satisfiability of Formula (c)

Since there are assignments in which either sub-clause is true (such as \(a = \text{true}, b = \text{true}, c = \text{true}\) or \(a = \text{false}, b = \text{false}, c = \text{false}\)), the formula is satisfiable.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

DNF (Disjunctive Normal Form)
DNF, or Disjunctive Normal Form, is a way of structuring logical expressions. In DNF, a formula is composed of a series of disjunctions (logical ORs) of conjunctions (logical ANDs) of literals. For example, a formula like \((a \wedge b) \vee c\) is in DNF. Here, \((a \wedge b)\) and \(c\) are the conjunctions combined by a disjunction.

This structure gives DNF a particular advantage when analyzing logical statements for satisfiability. Each conjunction, or clause, is considered individually. A DNF formula is satisfiable if there is at least one clause that can be made true by some assignment of truth values to its variables.

When solving problems in logic, especially in satisfiability problems, rewriting a formula in DNF can simplify the process. It allows you to focus on each clause independently. A simple tip for recognizing DNF is to look for clauses linked by \(\vee\) where each clause is a chain of \(\wedge\) operations.
Contradiction in Logic
Understanding contradictions is crucial when working with logical formulas. A contradiction occurs when a logical expression is inherently false, no matter the truth values assigned to its variables. It often arises when a variable and its negation appear in the same conjunction, such as \(c \wedge eg c\). This scenario is always false because a statement and its negation cannot both be true simultaneously.

In the context of DNF, identifying contradictions helps determine the satisfiability of a formula. If a clause contains a contradiction, that clause can never contribute to making the entire formula true. For instance, in the DNF formula \((b \wedge eg b)\), regardless of any truth assignment, this clause is false.

To solve satisfiability problems, pinpoint clauses with contradictions and consider them as irrelevant for achieving a true formula status. Thus, you focus only on the clauses without contradictions.
Truth Assignment
Truth assignment is the process of determining the truth values (true or false) for the variables in a logical formula. It is essential for establishing whether a formula is satisfiable. Essentially, you're assigning 'true' or 'false' to individual variables to evaluate the formula's overall truthfulness.

In DNF formulas, a truth assignment that makes any one clause true makes the entire formula satisfiable. For example, consider the formula \((a \wedge b \wedge c) \vee (eg a \wedge eg b \wedge eg c)\). You can assign truth values such as \(a = \text{true}, b = \text{true}, c = \text{true}\) for the first clause or \(a = \text{false}, b = \text{false}, c = \text{false}\) for the second. Both truth assignments satisfy the formula.

When analyzing logical expressions, look for truth assignments that fulfill at least one clause without contradiction. If such truth assignments exist, the formula is satisfiable. Hence, becoming skilled in truth assignment is a significant step toward understanding logical expressions and their satisfiability.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Let \(\phi=(p \rightarrow q) \rightarrow((r \wedge \neg s) \rightarrow q)\). For each of the following interpretations of \(p, q, r,\) and \(s,\) compute \(I(\phi)\) using the truth tables for \(\neg, v, \wedge, \rightarrow,\) and \(\leftrightarrow\) (a) \(I(p)=T, I(q)=T, I(r)=F,\) and \(I(s)=T\) (b) \(I(p)=T, I(q)=F, I(r)=T,\) and \(I(s)=F\) (c) \(I(p)=F, I(q)=T, I(r)=T,\) and \(I(s)=F\) (d) \(I(p)=F, I(q)=F, I(r)=T,\) and \(I(s)=F\)

Translate each of the following quantified formulas into an English sentence where the universal set is \(\mathbb{R}\). Label each as true or false. (a) \(\forall x(\exists y(x y=x))\) (b) \(\forall y(\exists x(x y=x))\) (c) \(\forall x(\exists y(x y=1))\) (d) \(\exists y(\forall x \neq 0(x y=1))\) (e) \(\exists x(\forall y(x y=x))\) (f) \((\forall x(x \neq 0 \rightarrow \exists y(x y=1))\)

The length of a clause is the number of literals in the clause. The length of a CNF formula is the sum of the length of its clauses. The number of excess literals in a CNF formula is the length of the formula minus the number of clauses in the formula. (a) Show that if an unsatisfiable set \(S\) of clauses contains only clauses of length 0 and 1 , it has a resolution refutation. (Hint: Prove the following: If \(S\) contains a clause of length 0 , it has [trivially] a resolution refutation. If, for some proposition letter \(p, S\) contains both \(p\) and \(\neg p,\) then \(S\) has a resolution refutation. Otherwise, \(S\) is satisfiable.) (b) Show that if a set \(\left\\{\lambda_{1} \vee \lambda_{2} \vee \ldots \vee \lambda_{k} \vee \lambda_{k+1}+\cup S(k \geq 1)\right.\) of clauses is un- satisfiable, so are \(\left\\{\lambda_{1} \vee \lambda_{2} \vee \lambda_{k}\right\\} \cup S\) and \(\left\\{\lambda_{k+1}\right\\} \cup S\). (Hint: For the first half, prove that if an interpretation \(I\) satisfies \(\left\\{\lambda_{1} \vee \lambda_{2} \vee \ldots \vee \lambda_{k}\right\\} \cup S,\) it also satisfies \(\left.\left\\{\lambda_{1} \vee \lambda_{2} \vee \cdots \vee \lambda_{k} \vee \lambda_{k+1}\right\\} \cup S_{.}\right)\) (c) Show that for \(k \geq 1,\) the number of excess literals in \(\left\\{\lambda_{1} \vee \lambda_{2} \vee \cdots \vee \lambda_{k}\right\\} \cup S\) and the number of excess literals in \(\left\\{\lambda_{k+1}\right\\} \cup S\) are both less than the number of excess literals in \(\left\\{\lambda_{1} \vee \lambda_{2} \vee \ldots \vee \lambda_{k} \vee \lambda_{k+1}\right\\} \cup S\). (d) A resolution derivation of a clause \(r_{k}\) from a set \(S\) of clauses is a sequence \(r_{0}, r_{1}, r_{2}, \ldots, r_{k}\) of clauses where each \(r_{l}\) is either an element of \(S\) or a resolvant of two previous \(r\) 's. (Thus, resolution refutation of \(S\) is just a resolution derivation of \(F\) from \(S .\) ) Show that if there is a resolution derivation of \(\lambda\) from \(S\) and a resolution refutation of \(S \cup\\{\lambda\\},\) then there is a resolution refutation of \(S .\) (e) Prove that if there is a resolution refutation \(\rho\) of \(\left\\{\lambda_{1} \vee \lambda_{2} \vee \ldots \vee \lambda_{k}\right\\} \cup S,\) then either (i) there is a resolution refutation of \(\left.\mid \lambda_{1} \vee \lambda_{2} \vee \cdots \vee \lambda_{k} \vee \lambda_{k+1}\right\\} \cup S\) or (ii) there is a resolution derivation of \(\lambda_{k+1}\) from \(\lambda_{1} \vee \lambda_{2} \vee \ldots \vee \lambda_{k} \vee \lambda_{k+1} \cup S\). (Hint: Prove this by induction on the length \(\rho\). You will have to add \(\lambda_{k+1}\) as a disjunct to some of the clauses in \(\rho\). It is not true in general that if \(S \models \lambda\), then there is a resolution derivation of \(\lambda\) from \(S .\) ) (f) Prove that resolution refutation is complete.

For any two integers \(m\) and \(n,\) we say \(m\) divides \(n\) if there is an integer \(k\) such that \(n=\) \(m k\). (Many programming languages give easy ways to say that, such as \(n \% m=0\) or \(n\) div \(m=0 .\) ) Define \(D i v(m, n)\) to be \(m\) divides \(n\). Translate each of the following propositions and quantified formulas into a clear English sentence. Label each as being true or false, with the universe as the set \(\mathbb{Z}\). (a) \(\operatorname{Div}(5,7)\) (b) \(\operatorname{Div}(4,16)\) (c) \(\operatorname{Div}(16,4)\) (d) \(\operatorname{Div}(-8,0)\) (e) \(\forall m(\forall n(\operatorname{Div}(m, n)))\) (f) \(\forall n(\operatorname{Div}(1, n))\) (g) \(\forall m(\operatorname{Div}(m, 0))\) (h) \(\forall m(\forall n(\operatorname{Div}(m, n) \rightarrow \operatorname{Div}(n, m)))\) (i) \(\forall m(\forall n(\forall p((D i v(m, n) \wedge \operatorname{Div}(n, p)) \rightarrow \operatorname{Div}(m, p))))\) (j) \(\forall m(\forall n((D i v(m, n) \wedge \operatorname{Div}(n, m)) \rightarrow m=n))\)

Write the truth tables for the following formulas, Use the truth table to determine whether any of these formulas is a tautology. (a) \(((p \rightarrow q) \wedge(q \rightarrow r)) \rightarrow(p \leftrightarrow r)\) (b) \(((p \rightarrow q) \wedge(q \rightarrow r)) \rightarrow(p \rightarrow r)\) (c) \(((p \rightarrow q) \rightarrow r) \rightarrow(p \rightarrow(q \rightarrow r))\) (d) \((p \rightarrow(r \vee q)) \rightarrow((p \rightarrow r) \vee(p \rightarrow q))\) (e) \((p \rightarrow(r \wedge q)) \rightarrow((p \rightarrow r) \vee(p \rightarrow q))\) (f) \(((p \rightarrow q) \rightarrow q) \rightarrow p\)
See all solutions

Recommended explanations on Computer Science Textbooks

Cloud Services

Read Explanation

Computer Systems

Read Explanation

Theory of Computation

Read Explanation

Computer Organisation and Architecture

Read Explanation

Issues in Computer Science

Read Explanation

Databases

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free