The document Propositional and First Order logic Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Mock Test Series - Computer Science Engg. (CSE) GATE 2020.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**Mathematical Logic | Propositional Logic | Introduction**

**Propositions**

A Proposition is declarative sentence which is either TRUE or FALSE, but not both.

Some examples of Propositions

(1) Delhi is capital of India.

(2) 2 + 2 = 5

(3) 1 + 1 = 2

(2) 2 + 2 = 5

(3) 1 + 1 = 2

All the above are proposition as they can be true or false but not both.

Some examples of sentence which are not proposition.

(1) 1 + x = 5.

(2) It will rain tomorrow.

(2) It will rain tomorrow.

All above examples are not proposition, they can be either be true or false.

**Negation of Proposition**

Negation of p is denoted by ‘¬p’, is the statement

It is not the case p.

Some Examples

(1) Find out negation of the proposition.

“Aman runs very fast”

Solution: It is not the case that aman runs very fast.

In simpler terms “Aman does’t runs fast”.

**Disjunction**

Disjunction of p and q, denoted by p ∨ q, is the proposition ‘p or q’. The Disjunction p ∨ q is TRUE when anyone of p or q is TRUE.

**Truth Table**

**Conjunction**

Conjunction of p and q, denoted by p∧q, is the proposition ‘p and q’. The Conjunction p∧q is TRUE when both p and q are TRUE.

**Truth Table**

**Logical Implication**

It is a type of relationship between two statements or sentence. Denoted by ‘p → q’.

In English implication can be written as following:

if p then q p implies q

if p, q p only if q

q when p p is sufficient for q

if p, q p only if q

q when p p is sufficient for q

The conditional statement p → q is false when p is true and q is false, and true otherwise.

Example: ‘if India wins, i will give party’.

Here p is India wins.

q is i will give party.

**Truth Table**

**Bi-Condition**

A bi-conditional statement is a compound statement formed by combining two conditionals under “and.” Bi-conditionals are true when both statements have the exact same truth value.

In English Bi-Conditional can be written as follows:

p is necessary and sufficient for q.

"if p then q" and "if q then p"

p if and only if q

p iff q

**Truth Table**

** Tautology** : A compound proposition which is always true.

** Contradiction** : A compound proposition which is always false.

** Contingency** : A compound statement which is neither true or neither false under every possible values. A contingency is neither a Tautology nor a Contradiction. In other words, a formula is contingency if the formula and its complement both are satisfiable (There exist entry in truth table for which the compound formula is true and there also exist an entry for which false)

**Examples**

let ‘p’ be a compound proposition

p ∨¬p is a tautology.

p ∧¬p is a contradiction.

x > 4 is contingency as it can be true for some values

and false for some values.

p ∧¬p is a contradiction.

x > 4 is contingency as it can be true for some values

and false for some values.

**Logical Equivalences**

Those compound proposition which have same truth values in all possible cases are known as**.**

Denoted by ‘≡’ or ‘⇔’ symbol.

Example 1. Show that p → q and ¬p ∨ q are equivalent.

Solution: We can construct truth table to show equivalence.

As seen from Truth table, ‘p → q’ and ‘¬p ∨ q’ have same truth values. So we can say p → q ≡ ¬p ∨ q.

**Some Useful Equivalence**

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

**Predicates**

A predicate is a Boolean-valued function on some variable(s). Let see some example predicates.

"x > 10"

"x = y + 3"

"x = y + 3"

The first statement “x is greater than 10″ has two parts, “x” is the **subject** of the statement and “is greater than 10″ is **predicate**. Statement “x is greater than 10″ can be denoted by **P(x)**, where P denotes the predicate and x is the variable.

**Example 1:** Let P(x) denote the statement “x > 10″. What are the truth values of P(11) and P(5)?**Solution :**

P(11) means 11 > 10, which is TRUE.

P(5) means 5 > 10, which is FALSE.

**Example 2:** Let R(x,y) denotes the statement ” x = y + 1″. What is the truth value of the proposition R(1,3) and R(2,1) ?**Solution :**** **R(1,3), 1 = 3 + 1 is FALSE. R(2,1), 2 = 1 + 1 is TRUE.

**Quantifier**

In logic, quantification is a construct that specifies the quantity of specimens in the domain of discourse that satisfy an open formula. For example, in arithmetic, it allows the expression of the statement that every natural number has a successor. A language element which generates a quantification (such as “every”) is called a **quantifier**

**Universal Quantifier**

Universal Quantification of a predicate P(x) means

P(x) for all values of x in its domain

‘∀’ is used to represent **universal quantifier.**

**Example 1:** Let P(x) be the statement ” x + 2 > x” . What is the truth value of the ∀xP(x).

**Solution :** As x+2 is greater than x for any real number , so ∀xP(x) is always TRUE.

**Existential Quantifier **

Existential Quantification of a predicate P(x) means

There exists an element x in the domain such that P(x).

‘∃’ is known as **existential quantifier**

**Example : **Let P(x) be the statement “x>5″. What is the truth value of the ∃xP(x) ?**Solution :** For some real number such as x = 4, ∃xP(x) is also true.

**Negating Quantified Expression**

¬∀xP(x) ≡ ¬P(x)

¬∃xQ(x) ≡ ∀x ¬Q(x)

¬∃xQ(x) ≡ ∀x ¬Q(x)

**Example :** What is the negation of “There is an honest man” ?**Solution:** Let say H(x) denotes x is honest man. So the statement can be written as ∃x H(x).

negation of ∃x H(x) using above results is ∀x ¬H(x)

**Nested quantifier**

Two quantifier are nested if one is within scope of other.

For example :

∀x∃y(x + y = 0).

In the above example we have two quantifier ‘∀’ and ‘∃’ with in scope of each other.

In English we can read it as ‘for all x, there exist a y for which x+y becomes 0.’

**Example 1 :** Translate the following statement into English.

∀x∃y(x = -y), x and y belongs to real number.**Solution : **For every real number x, there is a real number y such that x = -y.

**Example 2:** Translate the following statement into English.

∀x∀y((x > 0) ∧ (y > 0) → (x +y > 0)) ,Domain Real Numbers**Solution :** For two positive integers, the sum of these integers is positive.

OR in simpler terms, Sum of two positive number is positive.

**Order of quantifier**

Order of quantifier is important, unless all quantifier are universal(∀) or all are existential(∃)

∀x∀y P(x,y) is same as ∀y∀x P(x,y).

∃x∃y Q(x,y) is same as ∃y∃x Q(x,y).

∃y R(x,y) is not same as ∀y∃x R(x,y).

∃x∃y Q(x,y) is same as ∃y∃x Q(x,y).

∃y R(x,y) is not same as ∀y∃x R(x,y).

**Example : **Translate the following into logical expression.

“If a person is a student and is computer science major, then this person takes a course in mathematics.”**Solution:**

P(x) : x is student.

Q(x) : x is computer science major.

R(x,y) : x takes y course.

∀x (P(x) ∧ Q(x) ) → ∃y R(x,y).

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

131 docs|169 tests

### Combinatorics

- Doc | 7 pages
### Relations

- Doc | 4 pages
### Groups

- Doc | 1 pages
### Sets

- Doc | 4 pages