UNIT-I MATHEMATICAL LOGIC & BOOLEAN ALGEBRA: CSE BTECH 4TH SEM

TOPIC-

  1. Basic concept of mathematical logic,
  2. Statements,Connectives,
  3. Conditional and biconditional statements,
  4. Logical equivalence,
  5. Logical implication & quantifiers,
  6. Basic concept of Boolean Algebra,
  7. Properties of Boolean Algebra,
  8. Boolean functions,
  9. Disjunctive & conjunctive normal forms of Boolean functions,
  10. Applications of Boolean Algebra in switching circuits & logic circuits.

1. Basic concept of mathematical logic, BOOLEAN ALGEBRA:

Mathematical logic, also called formal logic, is a subfield of mathematics exploring the applications of formal logic to mathematics. It bears close connections to metamathematics, the foundations of mathematics, philosophy, and theoretical computer science.[a] The unifying themes in mathematical logic include the study of the expressive power of formal systems and the deductive power of formal proof systems. Mathematical logic is often divided into the fields of set theory, model theory, recursion theory, and proof theory. These areas share basic results on logic, particularly first-order logic, and definability. In computer science (particularly in the ACM Classification) mathematical logic encompasses additional topics not detailed in this article; see Logic in computer science for those.

2.Statements,Connectives,

Statement ­ A sentence that can be judged either true or false
Simple statement ­ a sentence that conveys only one idea.
ex. The Brooklyn Bridge goes over San Francisco Bay
Compound Statement ­ a sentence that conveys more than one idea which
are linked by connectives.
ex. I will go to the birthday party or I will send a present

3.Conditional and biconditional statements,

Conditional Statement

Let p and q are two statements then “if p then q” is a compound statement, denoted by p→ q and referred as a conditional statement, or implication. The implication p→ q is false only when p is true, and q is false; otherwise, it is always true. In this implication, p is called the hypothesis (or antecedent) and q is called the conclusion (or consequent).

p q p → q
T T T
T F F
F T T
F F T

For Example: The followings are conditional statements.

  1. If a = b and b = c, then a = c.
  2. If I get money, then I will purchase a compute

BiConditional Statement

If p and q are two statements then “p if and only if q” is a compound statement, denoted as p ↔ q and referred as a biconditional statement or an equivalence. The equivalence p ↔ q is true only when both p and q are true or when both p and q are false.

p q p ↔ q
T T T
T F F
F T F
F F T

For Example: (i) Two lines are parallel if and only if they have the same slope.
(ii) You will pass the exam if and only if you will work hard.

Example: Prove that p ↔ q is equivalent to (p →q) ∧(q→p).

Solution: Construct the truth table for both the propositions:

4.Logical equivalence,

In logic and mathematics, statements {\displaystyle p} and {\displaystyle q} are said to be logically equivalent if they are provable from each other under a set of axioms,[1] or have the same truth value in every model.[2] The logical equivalence of {\displaystyle p} and {\displaystyle q} is sometimes expressed as {\displaystyle p\equiv q}{\displaystyle p::q},[3] {\displaystyle {\textsf {E}}pq}, or {\displaystyle p\iff q}, depending on the notation being used. However, these symbols are also used for material equivalence, so proper interpretation would depend on the context. Logical equivalence is different from material equivalence, although the two concepts are intrinsically related.

General logical equivalences[3][edit]

Equivalence Name
{\displaystyle p\wedge \top \equiv p}
{\displaystyle p\vee \bot \equiv p}
Identity laws
{\displaystyle p\vee \top \equiv \top }
{\displaystyle p\wedge \bot \equiv \bot }
Domination laws
{\displaystyle p\vee p\equiv p}
{\displaystyle p\wedge p\equiv p}
Idempotent or tautology laws
{\displaystyle \neg (\neg p)\equiv p} Double negation law
{\displaystyle p\vee q\equiv q\vee p}
{\displaystyle p\wedge q\equiv q\wedge p}
Commutative laws
{\displaystyle (p\vee q)\vee r\equiv p\vee (q\vee r)}
{\displaystyle (p\wedge q)\wedge r\equiv p\wedge (q\wedge r)}
Associative laws
{\displaystyle p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)}
{\displaystyle p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)}
Distributive laws
{\displaystyle \neg (p\wedge q)\equiv \neg p\vee \neg q}
{\displaystyle \neg (p\vee q)\equiv \neg p\wedge \neg q}
De Morgan’s laws
{\displaystyle p\vee (p\wedge q)\equiv p}
{\displaystyle p\wedge (p\vee q)\equiv p}
Absorption laws
{\displaystyle p\vee \neg p\equiv \top }
{\displaystyle p\wedge \neg p\equiv \bot }
Negation laws

Logical equivalences involving conditional statements[edit]

  1. {\displaystyle p\implies q\equiv \neg p\vee q}
  2. {\displaystyle p\implies q\equiv \neg q\implies \neg p}
  3. {\displaystyle p\vee q\equiv \neg p\implies q}
  4. {\displaystyle p\wedge q\equiv \neg (p\implies \neg q)}
  5. {\displaystyle \neg (p\implies q)\equiv p\wedge \neg q}
  6. {\displaystyle (p\implies q)\wedge (p\implies r)\equiv p\implies (q\wedge r)}
  7. {\displaystyle (p\implies q)\vee (p\implies r)\equiv p\implies (q\vee r)}
  8. {\displaystyle (p\implies r)\wedge (q\implies r)\equiv (p\vee q)\implies r}
  9. {\displaystyle (p\implies r)\vee (q\implies r)\equiv (p\wedge q)\implies r}

Logical equivalences involving biconditionals[edit]

  1. {\displaystyle p\iff q\equiv (p\implies q)\wedge (q\implies p)}
  2. {\displaystyle p\iff q\equiv \neg p\iff \neg q}
  3. {\displaystyle p\iff q\equiv (p\wedge q)\vee (\neg p\wedge \neg q)}
  4. {\displaystyle \neg (p\iff q)\equiv p\iff \neg q}

5.Logical implication & quantifiers,

Logical implication

Logical implication is a type of relationship between two statements or sentences. The relation translates verbally into “logically implies” or “if/then” and is symbolized by a double-lined arrow pointing toward the right ( implies). If A and B represent statements, then A impliesB means “A implies B” or “If A, then B.” The word “implies” is used in the strongest possible sense.

As an example of logical implication, suppose the sentences A and B are assigned as follows:

A = The sky is overcast.
B = The sun is not visible.

In this instance, A impliesB is a true statement (assuming we are at the surface of the earth, below the cloud layer.) However, the statement B impliesA is not necessarily true; it might be a clear night. Logical implication does not work both ways. However, the sense of logical implication is reversed if both statements are negated. That is,

(A impliesB) implies(-B implies-A)

Using the above sentences as examples, we can say that if the sun is visible, then the sky is not overcast. This is always true. In fact, the two statements A impliesB and -B implies-A are logically equivalent.

Logical quantifiers,

In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula. For instance, the universal quantifier {\displaystyle \forall } in the first order formula {\displaystyle \forall xP(x)} expresses that everything in the domain satisfies the property denoted by {\displaystyle P}. On the other hand, the existential quantifier {\displaystyle \exists } in the formula {\displaystyle \exists xP(x)} expresses that there is something in the domain which satisfies that property. A formula where a quantifier takes widest scope is called a quantified formula. A quantified formula must contain a bound variable and a subformula specifying a property of the referent of that variable.

The mostly commonly used quantifiers are {\displaystyle \forall } and {\displaystyle \exists }. These quantifiers are standardly defined as duals and are thus interdefinable using negation. They can also be used to define more complex quantifiers, as in the formula {\displaystyle \neg \exists xP(x)} which expresses that nothing has the property {\displaystyle P}. Other quantifiers are only definable within second order logic or higher order logics. Quantifiers have been generalized beginning with the work of Mostowski and Lindström.

6.Basic concept of Boolean Algebra,

What Is Boolean Algebra?

Boolean algebra is a division of mathematics that deals with operations on logical values and incorporates binary variables. Boolean algebra traces its origins to an 1854 book by mathematician George Boole.

The distinguishing factor of Boolean algebra is that it deals only with the study of binary variables. Most commonly Boolean variables are presented with the possible values of 1 (“true”) or 0 (“false”). Variables can also have more complex interpretations, such as in set theory. Boolean algebra is also known as binary algebra.

Understanding Boolean Algebra

Boolean algebra is different from elementary algebra as the latter deals with numerical operations and the former deals with logical operations. Elementary algebra is expressed using basic mathematical functions, such as addition, subtraction, multiplication, and division, whereas Boolean algebra deals with conjunction, disjunction, and negation.

The concept of Boolean algebra was first introduced by George Boole in his book, The Mathematical Analysis of Logic, and further expanded upon in his book, An Investigation of the Laws of Thought. Since its concept has been detailed, Boolean algebra’s primary use has been in computer programming languages. Its mathematical purposes are used in set theory and statistics.

7.Properties of Boolean Algebra,

  • Boolean algebra is a branch of mathematics that deals with operations on logical values with binary variables.
  • The Boolean variables are represented as binary numbers to represent truths: 1 = true and 0 = false.
  • Elementary algebra deals with numerical operations whereas Boolean algebra deals with logistical operations.
  • Boolean algebra utilizes conjunction, disjunction, and negation, as opposed to addition, subtraction, multiplication, and division.
  • The primary modern use of Boolean algebra is in computer programming languages.
  • In finance, Boolean algebra is used in binomial options pricing models, which helps determine when an option should be exercised.

8.Boolean functions,

In mathematics, a Boolean function is a function whose arguments, as well as the function itself, assume values from a two-element set (usually {true, false}, {0,1} or {-1,1}).[1][2] Alternative names are switching function, used especially in older computer science literature,[3][4] and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory.[5]

A Boolean function takes the form {\displaystyle f:\{0,1\}^{k}\to \{0,1\}}, where {\displaystyle \{0,1\}} is known as the Boolean domain and {\displaystyle k} is a non-negative integer called the arity of the function. In the case where {\displaystyle k=0}, the “function” is a constant element of {\displaystyle \{0,1\}}. A Boolean function with multiple outputs, {\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}} with {\displaystyle m>1} is a vectorial or vector-valued Boolean function (an S-box in cryptography).[6]

There are {\displaystyle 2^{2^{k}}} different Boolean functions with {\displaystyle k} arguments; equal to the number of different truth tables with {\displaystyle 2^{k}} entries.

Every {\displaystyle k}-ary Boolean function can be expressed as a propositional formula in {\displaystyle k} variables {\displaystyle x_{1},…,x_{k}}, and two propositional formulas are logically equivalent if and only if they express the same Boolean function.

9.Disjunctive & conjunctive normal forms of Boolean functions

A logical formula is considered to be in DNF if it is a disjunction of one or more conjunctions of one or more literals.[1]:153 A DNF formula is in full disjunctive normal form if each of its variables appears exactly once in every conjunction. As in conjunctive normal form (CNF), the only propositional operators in DNF are and ({\displaystyle \wedge }), or ({\displaystyle \vee }), and not ({\displaystyle \neg }). The not operator can only be used as part of a literal, which means that it can only precede a propositional variable.

The following is a context-free grammar for DNF:

  1. disjunction → (conjunction {\displaystyle \vee } disjunction)
  2. disjunction → conjunction
  3. conjunction → (literal {\displaystyle \wedge } conjunction)
  4. conjunction → literal
  5. literal → {\displaystyle \neg }variable
  6. literal → variable

Where variable is any variable.

For example, all of the following formulas are in DNF:

  • {\displaystyle (A\land \neg B\land \neg C)\lor (\neg D\land E\land F)}
  • {\displaystyle (A\land B)\lor C}
  • {\displaystyle A\land B}
  • {\displaystyle A}

However, the following formulas are not in DNF:

  • {\displaystyle \neg (A\lor B)}, since an OR is nested within a NOT
  • {\displaystyle \neg (A\land B)\lor C}, since an AND is nested within a NOT
  • {\displaystyle A\lor (B\land (C\lor D))}, since an OR is nested within an AND

The formula {\displaystyle A\lor B} is in DNF, but not in full DNF; an equivalent full-DNF version is {\displaystyle (A\land B)\lor (A\land \lnot B)\lor (\lnot A\land B)}.

Conjunctive normal form

Conjunctive normal form (CNF) is an approach to Boolean logic that expresses formulas as conjunctions of clauses with an AND or OR. Each clause connected by a conjunction, or AND, must be either a literal or contain a disjunction, or OR operator. CNF is useful for automated theorem proving.

In conjunctive normal form, statements in Boolean logic are conjunctions of clauses with clauses of disjunctions. In other words, a statement is a series of ORs connected by ANDs.

For example:

(A OR B) AND (C OR D)

(A OR B) AND (NOT C OR B)

The clauses may also be literals:

A OR B

A AND B

Literals are seen in CNF as conjunctions of literal clauses and conjunctions that happen to have a single clause. It is possible to convert statements into CNF that are written in another form, such as disjunctive normal form.

10.Applications of Boolean Algebra in switching circuits & logic circuits

Application of Boolean algebra to the logical design of switching circuits is discussed. It is pointed out that for the design of a circuit requiring the minimum number of elements the Boolean function must be minimized by either an algebraic or a graphical method. A graphical method developed at the Institute of Mathematical Machines, Czechoslovakia, for minimizing a Boolean function is described.

0
Open chat