Home »
Discrete Mathematics
Operations in Propositional Logic in Discrete Mathematics
In this tutorial, we will learn about the basic operations and the truth table of the preposition logic in discrete mathematics.
By Prerana Jain Last updated : May 09, 2023
1. 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.
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,
2. 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 |
3. 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 |
4. 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