Scribd
Upload
8 views13 pages

Truth Tables and Normal Forms Explained

The document discusses normal forms in logic, specifically disjunctive normal form (DNF) and conjunctive normal form (CNF), which are used to determine if a statement formula is a tautology or contradiction. It introduces basic terminologies such as elementary product and elementary sum, and outlines the process to obtain DNF and CNF for given formulas. The construction of truth tables is mentioned as impractical, leading to the necessity of reducing formulas to normal forms.

Uploaded by

arna.adhikari2024
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
8 views13 pages

Truth Tables and Normal Forms Explained

The document discusses normal forms in logic, specifically disjunctive normal form (DNF) and conjunctive normal form (CNF), which are used to determine if a statement formula is a tautology or contradiction. It introduces basic terminologies such as elementary product and elementary sum, and outlines the process to obtain DNF and CNF for given formulas. The construction of truth tables is mentioned as impractical, leading to the necessity of reducing formulas to normal forms.

Uploaded by

arna.adhikari2024
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

Normal Forms

 If a given statement formula A(p1, p2, ...pn) involves n atomic


variables, we have 2n possible combinations of truth values of
statements replacing the variables.
 The problem of determining whether a given statement
formula is a Tautology, or a Contradiction is called a decision
problem.
 The construction of truth table involves a finite number of
steps, but the construction may not be practical.
 We therefore reduce the given statement formula to normal
form and find whether a given statement formula is a
Tautology or Contradiction.
 There are two types of normal form—disjunctive normal form
(DNF) and conjunctive normal form (CNF).
 It will be convenient to use the word product in place of
conjunction and sum in place of disjunction in our
current discussion.
Basic Terminologies:
 Elementary product: A product of the variables and their
negations (a conjunction of primary statements and their
negations) is called an elementary product.
 Elementary Sum: A sum of the variables and their negations
is called an elementary sum.
For example, are
some elementary products in 2 variables,
are some elementary sums is 2 variables.
 Disjunctive Normal Form: A compound proposition (or a
formula) which consists of a sum of elementary products
and which is equivalent to a given proposition is called a
disjunctive normal form (DNF) of the given proposition.
 Conjunctive Normal Form: A formula which consists of a
product of elementary sums and which is equivalent to a
given formula is called a conjunctive normal form (CNF) of
the given formula.
Procedure to Obtain the DNF or CNF of a Given Formula
 Find the disjunctive normal forms of the following
statements:
 Find the conjunctive normal forms of the following
statements:

You might also like