# Operations in preposition logic | Discrete Mathematics

In this article, we will learn about the **basic operations and the truth table of the preposition logic in discrete mathematics**.

Submitted by Prerana Jain, on August 31, 2018

## Tautologies and Contraction

Some proposition **P( p, q...)** contains the only **T** in the last column of their truth table or in other words, they are true for any values of their variables, such proposition are said to be tautologies. Analogously a proposition **P(p, q...)** is said to be a contradiction. If it contains the only **F** in the last column of its truth table or, in other words, if it is false for any truth values of its variables. For example, the proposition **"p or not p"**, that is **p V ~p**, is a tautology and the proposition **"p and not p"** that is **p ^ ~p** is a contradiction. This can be verified by looking at their truth tables.

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

T | F | T |

F | T | T |

The negation of a tautology is a contradiction since it is always false and the negation of a contradiction is a tautology since it is always true. Now suppose **P(p, q...)** is a tautology and suppose **P1(p,q...)**, **P2(p,q...)** are any proposition since **P(p,q...)** does not depend upon the practical truth values of its variables **p** ,**q...** we can substitute **p1 for p**, **P2 for q** in the tautology **P(p, q...)** and still have tautology. In other words,

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

T | F | F |

F | T | F |

### Logical equivalence

Two proposition **P(p,q...)** and **Q(p,q...)** is called logically equivalent, or simply equivalent or equal denoted by: **P(p, q...) = Q(p, q...)**.

If they have identical truth table. Consider for example the truth tables of **~(p ^ q)** and **~p v ~q** appearing in the table. Observe that both truth tables are the same that is both propositions are false in one case and true in the other three cases, according we can write: **~(p ^ q) = ~p V ~q**.

P | Q | P ^ Q | ~(p ^ Q) |
---|---|---|---|

T | T | T | F |

T | F | F | T |

F | T | F | T |

F | F | F | T |

P | Q | ~P | ~Q | ~P V ~Q |
---|---|---|---|---|

T | T | F | F | F |

T | F | F | T | T |

F | T | T | F | T |

F | F | T | T | T |

### Conditional and Biconditional statements

Many statements, particularly in mathematics are of them **"if p and q"**. Such statements are said to be the conditional statements is of the form **"p if and only if"**. Such statements are said to be bi-conditional statements are denoted by:

The truth table of **p → q** and **p ↔ q** are defined by the tables observe that:

- The conditional
**p → q**is false only when the first part**p**is true and the second part**q**is false. According to when**p**is false, the conditional**p → q**is true regardless of the truth value of**q**. - The biconditional says that the value of
**p**and**q**is true when they have the same truth values and otherwise the result is false. The truth table of the proposition**~p V q**appear in table observe that the truth tables of**~p V q**and**p↔**are identical that is they are both false only in the second case. Accordingly,**p → q**is logically equivalence to**~p V q**that is:**p → q = ~p v q**.

In other words the conditional statements **"if p and q"** are logically equivalent to the statements **"Not p or q"** which only involves the connectives **V** and **~** and this was already a part of our language. We must regard **p → q** as an abbreviation for an off-recurring statement.

**Conditional:**

p | Q | p → q |
---|---|---|

T | T | T |

T | F | F |

F | T | T |

F | F | T |

**Biconditional:**

P | Q | P ↔ Q |
---|---|---|

T | T | T |

T | F | F |

F | T | T |

F | F | T |

### Converse, Inverse and Contrapositive Proposition

If **p => q** is the direct proposition, then,

**q => p**is called its converse- The proposition
**~p => ~q**is called its inverse, and - The proposition
**~q => ~p**is called its contrapositive

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