# Preposition logic | Discrete Mathematics

In this article, we will learn about the **prepositions and statements and some basic logical operation in discrete mathematics**.

Submitted by Prerana Jain, on August 31, 2018

## Preposition or Statement

A preposition is a definition sentence which is true or false but not both.

**For example: ** The following 8 sentences,

- Paris in France
- 2 + 2 =4
- London in Denmark
- X = 2 is solution of x^2 = 4
- 1 + 1 = 2
- 9<6
- Where are you going?
- Do your homework

All of them are preposition except **vii** and **viii** moreover **i**, **ii** and **vi** are true whereas **iii**, **iv**, **v** are false.

### Compound proposition

Many propositions are composite that is composed of subpropositions and various connectives discussed subsequently. Such a composite proposition is said to be compound propositions. A proposition is called primitive if it cannot be broken down into the simpler proposition that is if it is not composite.

**Example:**

**"John intelligent or studies every night"**is a compound proposition with subproposition.**"John is intelligent"**and**"john studies every night"**.**"Roses are red and violets are blue"**is a compound proposition with subproposition**"Roses are red"**and**"violets are blue"**.

### Basic logical operation

The Three basic logical operations **conjunction**, **disjunction**, and **negation** which corresponds respectively. To the English words **"and"**, **"or"** and **"not"**.

**1) Conjunction (p ^ q):**

Any two proposition can be combined by the word and to form a compound proposition said to be the conjunction of the original proposition. Symbolically **p ^ q** read **p** and **q** denotes the conjunction of **p** and **q**. Since, **p ^ q** is a proposition it has the truth value and this truth value depends only on the truth values of **p** and **q**, specifically:

**Definition:** If **p** and **q** are true then **p ^ q** is true otherwise **p ^ q** is false.

p | q | p ^ q |
---|---|---|

T | T | T |

T | F | F |

F | T | F |

F | F | F |

**Example:** Consider the following 4 statements:

- Paris is in France
**and**2+2 = 4 - Paris is in France
**and**2 + 2 = 5 - Paris is in England
**and**2 + 2 = 4 - Paris is in England
**and**2 + 2 = 5

In the given four statements only the first statement is true. Each of the other statements is false since at least one of its substatements is false.

**2) Disjunction (p V q)**

Any two proposition can be combined by the word **"or"** to form a compound proposition is said to be the disjunction of the original proposition, symbolically **p V q**.

Read **"p or q"** denotes the disjunction of **p** and **q**. The truth value of **p V q** depends only on the truth values of **p** and **q** as follow:

**Definition:** If **p** and **q** are false then **p V q** is false, otherwise **p V q** is true.

p | q | pVq |
---|---|---|

T | T | T |

T | F | T |

F | T | T |

F | F | F |

**Example:** Consider the following four statements:

- Paris is in France
**or**2 + 2 = 4 - Paris is in France
**or**2 + 2 = 5 - Paris is in England
**or**2 + 2= 4 - Paris is in England
**or**2 + 2 = 5

Only the last statements are false. Each of the other statements is true since at least of its substatements is true.

**3) Negation( ~p)**

Given any proposition **p** another proposition is said to be the negation of **p** can be formed by writing - it is not the case that... or **"it is false that ..."**, before **p** or if possible by inserting in **p** the word **"not"** symbolically. **~p or ~p**.

Read **"not p"**, denotes the **negation of p**. The truth value of **p** depends on the truth value of **p** as follows:

**Definition:** If **p** is true then **~p** is false and if **p** is false then **~p** is true.

p | ~p |
---|---|

T | F |

F | ~F |

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions