Welcome to Edukum.com

Proposition and Truth function, Propositional Logic, Expressing statements in Logic Propositional Logic

Proposition
A proposition is a statement of either true or false. The purpose is to analyze these statements either individually or in a composite manner. A propositional consists of propositional variables and connectives. If a proposition is true we can say its true value is true, and if a proposition is false, we can say its true value is false.
Many mathematical statements are constructed by combining one or more propositions, new proposition called compound propositions,are formed from existing propositions using logical operations .

Example
6 + 9 = 18, is a proposition i.e. false.
Pound Sterling is the currency of United Kingdom, is a proposition of true statement.

Following is not a proposition
“A is less than 2 “ because unless we give a specific value of A and cannot say whether the statement is true or false.

Truth Function
Truth function is the truth value that can be observed in truth table with different propositional logic statements. A function that determines the truth value of a complex sentencesin the term of truth values of the component sentences without reference to their meaning.

Connectives
Five connectives are - OR (∨), AND ($\wedge$), Negation/NOT ($\lnot$), Implification/If then ($\to$), If and only if ($\Leftrightarrow$).

• OR ($\vee$)
OR operation is also known as Disjunction. Disjunction is ORing of two sentences. If we have two propositions p and q then if one of the two statements are true then the result will be true. T for True and F for False.  A B A $\vee$ B T T T T F T F T T F F F
• AND ($\wedge$)
AND operation is also known as Conjunction. Conjunction means ADDing two statements. If both the statements were true then the end result will be true. If one of the two is false then the result is false.
 A B A $\wedge$ B T T T T F F F T F F F F
• NOT ($\sim$)
NOT operation is also known as negation operation. Negation means that it is contradictory of the original one. If the statement is true then the result is false.  A $\sim$A T F F T

Propositional Logic
The rule of logic give meaning to mathematical statements are called proposition logic.
These rules are used to distinguish between valid and invalid mathematical arguments.
Proposition logic is also know as sentential logic or statemental logic that studies ways of joining and/or modifying entire propositons to form more comfortable propositions. In propositional logic the simplest statements are considered as indivisible units, and hence, the propositional logic doesnot study those logical properties and the relations that depend upon parts of statements.
It largely involves studying logical connectives as the words “AND “ and “OR” and the rules determining the truth values of the propositions they are used to join. These rules mean for validity of arguments and such logical relationships between statements as being consistent or in consistent with one another as well as logical properties of of propositons.
Propositon can be thought as a logical operators.A logical operator is any word used either to modify one statement to make a different statement or join together to form more complicated statement.Such as AND ,OR,NOT,If then,If and only if, are all operators.Some logical operators are not truth functional.
For example, both of the operations are true:
2 + 2 = 4.
Someone is reading an article in a philosophy encyclopedia.

Consider the corresponding statements modified with the operator “necessarily”:
Necessarily, 2 + 2 = 4.
Necessarily, someone is reading and article in a philosophy encyclopedia.
Here, the first example is true and the second is false.True or false of a statement using the operator “necessarily” does not depend entirely on the true or false of the statement modified.
Expressing statements in Logic Propositional Logic

Negation
Let p be the proposition. The negation of p, denoted by $\lnot$p.

Example

• Find the negation.
“Today is sunny”.
Solution:
The negation is “It is not the case that today is sunny”.
Also simply expressed as
“Today is not sunny”.
or
“It is not sunny”.
Truth table for negation:  P $\lnot$P T F F T

Conjunction
Suppose p and q are propositions. The conjunction of p and q, denoted by p $\wedge$ q is the proposition “p and q”. The conjunction p $\wedge$ q is true when both p and q are true and is false otherwise.

 p q p $\wedge$ q T T T T F F F T F F F F

Example

• Find the conjunction.
“Today is Friday” and q is proposition “It is raining today”.
Solution:
The conjunction of p & q is the proposition.
“Today is Friday and it is raining today”.
This proposition is true on rainy Friday and is false on any day that is not a Friday when it doesn’t rain.

Disjunction
The disjunction of p and q, denoted by p $\vee$ q, is the proposition p or q. The disjunction p and q is false when both p and q are false and is true otherwise.

 p q p $\vee$ q T T T T F T F T T F F F

Example

• Find the disjunction.
“Today is Sunday “ where p is proposition or q is propostion. “It is raining”.
Solution:
p$\vee$q is the proposition.
Today is Sunday or it is raining”.
The proposition is true on any day that is either a Sunday or a rainy day.It is only false on days that are not Sunday when it is also doesn’t rain.

Exclusive or of two Propositions
Let p and q be two propositions. The exclusive or of p and q , denoted by p $\oplus$ q, is the proposition that is true when exactly one of p and q is true and is false otherwise.

 p q p $\oplus$ q T T F T F T F T T F F F

Conditional Statements
The conditional statement p $\to$ q is the proposition if p then q. p $\to$ q is false when p is true and q is false, and true otherwise. In this statement , p is called hypothesis and q is the conclusion. Also called implications. The statement p $\to$ q is true when both p and q are true and when p is false.

 p q p $\to$ q T T T T F F F T T F F F

Example
Consider a statement that a professor might make- “If you get 100% on the final,then you will get an A”.
Converse, Contrapositive, Inverse:
The proposition q $\to$ p is called the converse of p $\to$ q.
The contrapositive of p $\to$ q is the proposition $\lnot$q $\to$ $\lnot$p.
The proposition $\lnot$p $\to$ $\lnot$q is called the inverse of p $\to$ q.

Example

• What are the contrapositive, the converse, and the inverse of the conditional statement ?
“The home team wins whenever it is raining”?
Solution:
q whenever p is one of the ways to express the conditional statement p $\to$ q, the original statement can be written as,
“If it is raining, then the home team wins”.
The contrapositive of this conditional statement is
“If the home team doesn’t win, then it is not raining”.
The converse is “If the home team wins, then it is raining”.
The inverse is “If it is not raining, then the home team doesn't win”.

Biconditionals
The biconditional statement p $\leftrightarrow$ q is the proposition “p if and only if q”. The statement is true when p and q have the same truth values, and is false otherwise. This is also called bi-implications.

 p q p $\leftrightarrow$ q T T T T F F F T F F F T

Questions

1. Construct the truth table of the compound proposition. (p $\vee$ $\lnot$q) $\to$ (p $\wedge$ q).
Solution:
The truth table involves p and q propositions.
 p q $\lnot$q p $\vee$ $\lnot$q p $\wedge$ q (p $\vee$ $\lnot$q) $\to$ (p $\wedge$ q) T T F T T T T F T T F F F T F F F T F F T T F F
2. Show that $\lnot$(p $\vee$ q) and $\lnot$(p $\vee$ q) are logical equivalents.
Solution:
$\lnot$(p $\vee$ q) and $\lnot$(p $\vee$ q) is,
 p q p $\vee$ q $\lnot$(p $\vee$ q) $\lnot$q $\lnot$ q $\lnot$p $\wedge$ $\lnot$q T T T T F F F T F T T F T F F T T T F F F F F F F T T T

Tautologies
A Tautology is a formula which is always true for every value of its propositional variables.

Example

• Prove [(A $\to$ B) $\wedge$ A] $\to$ B is a tautology
The truth table is as follows –  A B A $\to$ B (A $\to$ B) $\wedge$ A [(A $\to$ B) $\wedge$ A] $\to$ B T T T T T T F F F T F T T F T F F T F T

As we can see every value of [(A $\to$ B) $\wedge$ A] $\to$ B is “True”, it is a tautology.

A Contradiction is a formula which is always false for every value of its propositional variables.

Example

• Prove (A ∨ B) $\wedge$ [($\lnot$A) $\wedge$ ($\lnot$B)] is a contradiction
The truth table is as follows  A B A $\vee$ B $\lnot$A $\lnot$ B ($\lnot$A) $\wedge$ ($\lnot$B) (A $\vee$ B) $\wedge$ [($\lnot$A) $\wedge$ ($\lnot$ B)] T T T F F F F T F T F T F F F T T T F F F F F F T T T F

As we can see every value of (A ∨ B) $\wedge$ [($\lnot$A) $\wedge$ ($\lnot$B)] is “False”, it is a contradiction.

Contingency
A Contingency is a formula which has both some true and some false values for every value of its propositional variables.

Example

• Prove (A ∨ B) $\wedge$ ($\lnot$A) a contingency
The truth table is as follows −  A B A $\vee$ B $\lnot$A (A $\vee$ B) $\wedge$ ($\lnot$ A) T T T F F T F T F F F T T T T F F F T F

As we can see every value of (A ∨ B) $\wedge$ ($\lnot$A) has both “True” and “False”, it is a contingency.

Propositional Equivalences
Two statements X and Y are logically equivalent if any of the following two conditions −

• The truth tables of each statement have the same truth values.
• The bi-conditional statement X $\Leftrightarrow$ Y is a tautology.

Example

• Prove $\lnot$(A ∨ B) and [($\lnot$A) $\wedge$ ($\lnot$B)] are an equivalence.
Testing by 1st method  A B A $\vee$ B $\lnot$(A $\vee$ B) $\lnot$A $\lnot$B [($\lnot$A) $\wedge$ ($\lnot$ B)] T T T F F F F T F T F F T F F T T F T F F F F F T T T T
Here, we can see the truth values of $\lnot$ (A ∨ B) and [($\lnot$A) $\wedge$ ($\lnot$B)] are same, hence the statements are equivalent.
Testing by 2nd method(biconditionality)  A B $\lnot$ (A $\vee$ B) [($\lnot$A) $\wedge$ ($\lnot$B)] [$\lnot$ (A $\vee$ B)] $\Leftrightarrow$ [($\lnot$A) $\wedge$ ($\lnot$B)] T T F F T T F F F T F T F F T F F T T T
As [$\lnot$ (A ∨ B)] $\Leftrightarrow$ [($\lnot$A) $\wedge$ ($\lnot$B)] is a tautology, the statements are equivalent.

References

• H.Rosen, Kenneth.Discrete mathematics and its application, 7th edition.June 14,2011.
• http://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_propositional_logic.
• C.Klement, Kevin.University of Massachusetts,USA(http://www.iep.utm.edu/prop-log/)