# CS代考 CS2209A 2017 – cscodehelp代写

CS2209A 2017

Applied Logic for Computer Science

Lecture 8, 9 Propositional Logic:

Conjunctive Normal Form & Disjunctive Normal Form

Instructor: Xie

1

Conjunctive Normal Form (CNF)

• Resolutionworksbestwhentheformulaisofthe special form: it is an ∧ of ∨s of (possibly negated, ¬) variables (called literals).

• This form is called a Conjunctive Normal Form, or CNF. – ∨¬ ∧ ¬ ∧ ∨ isaCNF

– (∨¬∨) isaCNF.Sois ∧¬∧ .

– ∨ ¬∧ isnotaCNF

• An AND (∧) of CNF formulas is a CNF formula.

– So if all premises are CNF and the negation of the conclusion is a CNF, then AND of premises AND NOT conclusion is a CNF.

2

CNF

• To convert a formula into a CNF.

– Open up the implications to get ORs.

– Get rid of double negations.

–Convert ∨ ∧ to ∨ ∧ ∨ //distributivity

• Example: →(∧) ≡¬ ∨(∧) ≡¬∨∧¬∨

• In general, CNF can become quite big, especially when have ↔. There are tricks to avoid that …

3

Boolean functions and circuits

• Whatistherelationbetweenpropositionallogic and logic circuits?

– View a formula as computing a function (called a Boolean function),

• inputs are values of variables,

• output is either true (1) or false (0).

– For example, , , = when at least twooutof,,aretrue,and falseotherwise.

– Such a function is fully described by a truth table of its formula (or its circuit: circuits have truth tables too).

4

Boolean functions and circuits

• What is the relation between propositional logic and logic circuits?

– So both formulas and circuits “compute” Boolean functions – that is, truth tables.

– In a circuit, can “reuse” a piece in several places, so a circuit can be smaller than a formula.

• Still, most circuits are big!

– ,, is ∧ ∨ ∧ ∨ ∧

xy z

AND

AND OR AND

5

CNF and DNF

• Every truth table (Boolean function) can be written as either a conjunctive normal form (CNF) or disjunctive normal form (DNF)

• CNF is an ∧ of ∨s, where ∨ is over variables or their negations (literals); an ∨ of literals is also called a clause.

• DNFisan∨of∧s;an∧ofliteralsiscalleda term.

6

Notations

• ¬, , are examples of literals

• Neither¬¬nor(∨)isaliteral

• ∨¬∨ ,(¬)areclause

• ∧¬∧ ,(¬)areterms

• ∨¬∨ ∧(¬∨¬)∧ ¬ isaCNF

• ∧ ∨ ¬∧∧ ∨(¬∧)isaDNF

• ∧¬(∨)∨ isneitheraCNFnorDNF, butisequivalenttoDNF( ∧¬∧¬)∨

7

Facts about CNF and DNF

• Any propositional formula is tautologically equivalent to some formula in disjunctive normal form.

• Any propositional formula is tautologically equivalent to some formula in conjunctive normal form.

8

Why CNF and DNF?

• Convenient normal forms

• Resolution works best for formulas in CNF

• Useful for constructing formulas given a truth table

– DNF: take a disjunction (that is, ∨) of all satisfying truth assignments

– CNF: take a conjunction (∧) of negations of falsifying truth assignments

9

From truth table to DNF and CNF

• Amintermisaconjunctionofliteralsinwhich each variable is represented exactly once

– If a Boolean function (truth table) has the variables ,$, then∧¬$∧ isamintermbut∧¬$is

not.

• Each minterm is true for exactly one assignment.

–∧¬$∧istrue ifpistrue(1), qisfalse(0) and r is true (1).

– Any deviation from this assignment would make this particular minterm false.

• A disjunction of minterms is true only if at least one of its constituents minterms is true.

10

From truth table to DNF

• If a function, e.g. F, is given by a truth table, we know exactly for which assignments it is true.

pqr F

• Consequently, we can select the minterms that make the function true and form the disjunction of these minterms.

110 0

• Fistrueforthreeassignments: o p, q, r are all true, ( ∧ $ ∧ )

100 0 011 0 010 0 001 1 000 09,

o p, ¬q, r are all true, ( ∧ ¬$ ∧ )

o ¬p, ¬q, r are all true, (¬ ∧ ¬$ ∧ )

• DNFofF:(∧$∧)∨(∧¬$∧)∨ (¬ ∧ ¬$ ∧ )

111 1

101 1

11

From truth table to CNF

• Complementationcanbeusedtoobtainconjunctive normal forms from truth tables.

• IfAisaformulacontainingonlytheconnectives¬, ∨ and ∧ , then its complement is formed by

– replacing all ∨ by ∧

– replacing all ∧ by ∨

– replacing all atoms by their complements. • The complement of q is ¬q

• The complement of ¬q is q

• Example: Find the complement of the formula • (p∧q)∨¬r

(¬p∨¬q)∧r

12

From truth table to CNF

• Solution:¬Gistrueforthe following assignments.

pqr G 111 1 110 1 101 0 100 0 011 1 010 1 001 0 000 1

p=1; q=0; r=1 p=1; q=0; r=0 p=0; q=0; r=1

• The DNF of ¬G is therefore: (%∧¬&∧’)∨(%∧¬&∧¬’)∨(¬%∧¬&∧’)

• The formula has the complement: (¬%∨&∨¬’)∧ (¬%∨&∨’)∧(%∨&∨¬’)

It is the desired CNF of G

13

Canonical CNF and DNF

• Soforeveryformula,thereisauniquecanonical CNF (and a truth table, and a Boolean function).

• And for every possible truth table (a Boolean function), there is a formula (the canonical CNF).

• Recall,tomakeacanonicalDNFfromatruthtable: – Take all satisfying assignments.

– Write each as an AND of literals, as before. – Then take an OR of these ANDs.

14

Complete set of connectives

• CNFs only have ¬,∨,∧, yet any formula can be converted into a CNF

– Any truth table can be coded as a CNF

• Call a set of connectives which can be used to express any formula a complete set of connectives.

– In fact, ¬,∨ is already complete. So is ¬,∧ .

• ByDeMorgan, ∨ ≡¬(¬ ∧¬)Noneedfor∨!

– But ∧,∨ is not: cannot do ¬ with just ∧,∨.

• Because when both inputs have the same value, both ∧,∨

leave them unchanged.

15

Complete set of connectives

• How many connectives is enough?

– Just one: NAND (NotAND), also called the Sheffer

stroke, written as |

ABA|B

–¬≡|

True True False True False True False True True False False True

– ∨≡¬(¬ ∧¬) ≡¬ ¬)

≡ | ( |))

– In practice, most often stick to ∧,∨, ¬

16

Puzzle

• Susan is 28 years old, single, outspoken, and very bright. She majored in philosophy. As a student she was deeply concerned with issues of discrimination and social justice and also participated in anti-nuke demonstrations.

Please rank the following possibilities by how likely they are. List them from least likely to most likely. Susan is:

1. a kindergarden teacher

2. works in a bookstore and takes yoga classes

3. an active feminist

4. a psychiatric social worker

5. a member of an outdoors club

6. a bank teller

7. an insurance salesperson

8. a bank teller and an active feminist

17