Logic, which was originally just the study of what distinguishes sound argument from unsound argument, has now developed into a powerful and rigorous system whereby true statements can be discovered, given other statements that are already known to be true.

Predicate Logic

This logic deals with predicates, which are propositions containing variables.

A predicate is an expression of one or more variables defined on some specific domain. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable.

Following are a few examples of predicates −

• 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”

Propositional Logic

A proposition is a collection of declarative statements that have either a truth value “true” or a truth value “false”. A propositional consists of propositional variables and connectives. The propositional variables are dented by capital letters (A, B, etc). The connectives connect the propositional variables.

A few examples of Propositions are given below −

• “Man is Mortal”, it returns truth value “TRUE”
• “12 + 9 = 3 – 2”, it returns truth value “FALSE”

The following is not a Proposition −

• “A is less than 2” − It is because unless we give a specific value of A, we cannot say whether the statement is true or false.

Connectives

In propositional logic, we use the following five connectives −

• OR (∨∨)
• AND (∧∧)
• Negation/ NOT (¬¬)
• Implication / if-then (→→)
• If and only if (⇔⇔)

OR (∨∨)

The OR operation of two propositions A and B (written as A∨BA∨B) is true if at least any of the propositional variable A or B is true.

The truth table is as follows −

AND (∧∧)

The AND operation of two propositions A and B (written as A∧BA∧B) is true if both the propositional variable A and B is true.

The truth table is as follows −

Negation (¬¬)

The negation of a proposition A (written as ¬A¬A) is false when A is true and is true when A is false.

The truth table is as follows −

Implication / if-then (→→)

An implication A→BA→B is the proposition “if A, then B”. It is false if A is true and B is false. The rest cases are true.

The truth table is as follows −

If and only if (⇔⇔)

A⇔BA⇔B is a bi-conditional logical connective which is true when p and q are same, i.e., both are false or both are true.

The truth table is as follows −

Well Formed Formula

Well Formed Formula (wff) is a predicate holding one of the following −

• All propositional constants and propositional variables are wffs.
• If x is a variable and Y is a wff, ∀xY and ∃xY are also wff.
• Truth value and false values are wffs.
• Each atomic formula is a wff.
• All connectives connecting wffs are wffs.

Quantifiers

The variable of predicates is quantified by quantifiers. There are two types of quantifier in predicate logic −

• Universal Quantifier
• Existential Quantifier

Universal Quantifier

Universal quantifier states that the statements within its scope are true for every value of the specific variable. It is denoted by the symbol ∀.

∀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). Here, P(x) is the predicate which denotes that x is mortal and the universe of discourse is all men.

Existential Quantifier

Existential quantifier states that the statements within its scope are true for some values of the specific variable. It is denoted by the symbol ∃.

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

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

Nested Quantifiers

If we use a quantifier that appears within the scope of another quantifier, it is called a 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)