Discrete Mathematics Predicate Logic - Discrete Mathematics

What is predicate logic in Discrete Mathematics?

The predictions with respect to propositions are made by Predicate Logic.

Define Predicate Logic.

The expression of one or more variables are defined on the same specific domain, is defined as predicate. The variables predicate can be made on a proposition, either by assigning a value to the variable or by quantifying the variable.

Some of the examples of predicates are as follows:

  • Let E(x, y) denote "x = y"
  • Let X(a, b, c) denote "a + b + c = 0"
  • Let M(x, y) denote "x is married to y"

What is Well Formed Formula?

A predicate that holds any one of the following conditions is known as Well Formed Formula (wff).

  • All the propositional variables and propositional constants are Wffs.
  • If x is a variable and Y is a wff, ∀xY and ∃xY are also wff
  • The values of true and false are wffs
  • Each of the atomic formula is a wff
  • All the connectives that connect wffs are wffs

What are Quantifiers?

Quantifiers are used for quantifying the variables of prediction. The quantifiers in predicate logic are of two types - Universal Quantifier and Existential Quantifier.

Universal Quantifier

For every value of the specific variable, the statements within the scope are defined to be true by the universal quantifier and are denoted by ∀.

∀xP(x) is read as for every value of x, P(x) is true.

Example − "Man is mortal" can be transformed into the propositional form ∀xP(x) where P(x) is the predicate which denotes x is mortal and the universe of discourse is all men.

Existential Quantifier

For some of the values of specific variable, the statements within the scope are defined as true by existential quantifier and are denoted by ∃.

∃xP(x) is read as for some values of x, P(x) is true.

Example − "Some people are dishonest" can be transformed into the propositional form ∃xP(x) where P(x) is the predicate which denotes x is dishonest and the universe of discourse is some people.

Nested Quantifiers

When the quantifier that appears within the scope of another quantifier is used, it is known as nested quantifier.

Example

  • ∀ a∃bP(x,y) where P(a,b) denotes a+b=0
  • ∀ a∀b∀cP(a,b,c) where P(a,b) denotes a+(b+c)=(a+b)+c

Note ∀a∃bP(x,y)≠∃a∀bP(x,y)

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics