logical statements and truth tables

Logic

Statements, negations, connectives, truth tables, equivalent statements, De Morgan’s Laws, arguments, Euler diagrams

Part 1: Statements, Negations, and Quantified Statements

A statement is a sentence that is either true or false but not both simultaneously.

Ex:                        a. Paris is the capital of France;

b. Edgar Poe wrote the last episode of Monk.

Commands, questions, and opinions, are not statements because they are neither true nor false.

Ex:        a. Titanic is the greatest movie of all time. (opinion)

b.      Solve the exercises 20 – 50.(command)

c.       If I start losing my memory, how will I know? (question)

In symbolic logic, we use lowercase letters such as p, q, r, and s to represent statements.

Ex:                        p: Paris is the capital of France;

q: Edgar Poe wrote the last episode of Monk.

The negation of a statement has a meaning that is opposite that of the original meaning. The negation of a true statement is a false statement and the negation of a false statement is a true statement

Ex:        a. The negation of the statement “Edgar Poe wrote the last episode of Monk” can be

“Edgar Poe did not write the last episode of Monk” or also “It is not true that Edgar Poe wrote the last episode of Monk”

b. The negation of the statement “Today is not raining” is “Today is raining” or “It is not true that today is not raining”.

Symbolically, the negation of a statement p is denoted by ~p.

Ex:        p:            Today is Sunday;

~p:         Today is not Sunday.

The words all, some, and no (or none) are called quantifiers.

Ex: Statements containing a quantifier:

All poets are writers.

Some people are bigots.

No math books have pictures.

Some students do not work hard.

Equivalent Ways of Expressing Quantified Statements
Statement	Equivalent way to express it	Example
All A are B	There are no A that are no B	All teachers are trained;
		There are no teachers that are
		not trained.
Some A are B	There is at least one A that is	Some people like ice-cream;
	in B	At least one person likes ice-
		cream.
No A are B	All A are not B	No car is running on the rail
		train;
		All the cars are not running on
		the rail train.
Some A are not B	Not all A are B	Some students do not pass the
		class;
		Not all of the students are
		passing the class.

The statements diagonally opposite each other are negations.

All A are B

(There are no A that are no B)

Some A are B

(There is at least one A that is in B)

No A are B. (All A are not B)

Some A are not B (Not all A are B)

Here are some examples of quantified statements:

Symbolically, the universal statement “All A are B” can be written as “  A are B”, or “  A       B”.

The existential statement “Some A are B” can be written as “                 so that               ”

Ex: The mechanic told me, “All piston rings were replaced.” I later learned that the mechanic never tells the truth. What can we conclude?

Because the mechanic never tells the truth, we can Conclude that the truth is the negation of what I was told.

The negation of “All A are B” is “Some A are not B”. Thus, I can conclude that

Some piston rings were not replaced.

I can also correctly conclude that:

At least one piston ring was not replaced.

Part 2: Compound Statements and Connectives

Simple statements convey one idea with no connecting words.

Compound statements combine two or more simple statements using connectives. Connectives are words used to join simple statements. Examples are: and, or, if…then, and if and only if.

If p and q are two simple statements, then the compound statement “p and q” is symbolized by p q. The compound statement formed by connecting statements with the word and is called a conjunction. The symbol for and is .

Ex: Let p and q represent the following simple statements:

p: It is Sunday.

q: They are working.

The compound statement “It is Sunday and they are working” can be formally/symbolically expressed by “p q”.

The compound statement “It is Sunday and they are not working” can be formally/symbolically expressed by “p ~q”.

Common English Expressions for p   q
Symbolic Statement	English Statement	Example:
		p: It is Sunday.
		q: They are working.
p  q	p and q	It is Sunday and they are
		working.
p  q	p but q	It is Sunday, but they are
		working.
p  q	p yet q	It is Sunday, yet they are
		working.
p  q	p nevertheless q	It is Sunday; nevertheless they
		are working.

The connective or can mean two different things. Consider the statement “I visited New York City or Houston, TX.”

This statement can mean (exclusive or) “I visited New York City or Houston, TX but not both.”

It can also mean (inclusive or) “I visited New York City or Houston, TX or both.”

Disjunction is a compound statement formed using the inclusive or represented by the symbol

.

Thus, “p or q or both” is symbolized by p       q.

Ex: Let p and q represent the following simple statements:

p: The student prepared for the Test.

q: The student passed the Test.

The statement “The student prepared for the Test or the student passed the Test” can be written as “p q”.

The statement “The student prepared for the Test or the student did not pass the Test” can be written as “p ~q”.

The compound statement “If p, then q is symbolized by p q. This is called a conditional statement. The statement before the is called the antecedent. The statement after the is called the consequent.

Ex: This diagram shows a relationship that can be expressed 3 ways:

All men are mortal.

	There are no men that are not mortal.	Mortals
	If a person is a men, then that person is mortal.
		Men

Ex: Let p and q represent the following simple statements:
p: It is freezing.
q: It is cold.
The statement “If it is freezing then it is cold” can be written as “p			q”.
The statement “If it is not cold then it is not freezing” can be written as “~q   ~p”.
Common English expressions for p   q:
Symbolic Statement	English Statement		Example:
			p: It is freezing.
			q: It is cold.
p   q	If p then q		If it is freezing then it is cold.
p   q	q if p		It is cold if it is freezing.
p   q	p is sufficient for q		Being freezing is sufficient to
			be cold.
p   q	q is necessary for p		Being cold is necessary for
			being freezing.
p   q	p only if q		It is freezing only if it is cold.
p   q	Only if q, p		Only if it is cold is freezing.

Biconditional statements are conditional statements that are true if the statement is still true when the antecedent and consequent are reversed.

The compound statement “p if and only if q” (abbreviated as iff ) is symbolized by p         q.

Common English Expressions for p         q:

Symbolic Statement	English Statement	Example:
		p: It is 4th of July;
		q: It is the Independence Day.
p   q	p if and only if q	It is 4th of July if and only if it is
		the Independence Day.
p   q	q if and only if p	It is the Independence Day if
		and only if it is 4th of July.
p   q	If p then q, and if q then p.	If is 4th of July then is the
		Independence Day, and if is the
		Independence Day then is 4th of
		July.
p   q	p is necessary and sufficient	Being 4th of July is necessary
	for q	and sufficient for being the
		Independence Day.

p   q	q is necessary and sufficient	Being the Independence Day is
	for p	necessary and sufficient for
		being 4th of July.

Ex: Let p and q represent the following simple statements: p: She is laughing.

q: She is happy.

~(p  q):               “It is not true that she is laughing and is happy”;

~p  q:                   “She is not laughing and she is happy”;

~(p q): “She is neither laughing nor happy” or “”It is not true that she is laughing or is happy”

Expressing Symbolic Statements with Parentheses in English

Symbolic Statement	Statements to Group Together	English Translation
(q   ~p)   ~r	q   ~p	If q and not p, then not r.
q   ( ~p   ~r)	~p   ~r	q, and if not p then not r.

Remark: When we translate the symbolic statement into English, the simple statements in parentheses appear on the same side of the comma.

Ex: Let p, q, and r represent the following simple statements:

p: A student misses class.

q: A student studies.

r: A student fails.

a.       (q ~ p) ~ r: “If a student studies and does not miss class, then the student does not fail.”

b.      q (~p ~r): “A student studies, and if the student does not miss class, then the student does not fail.”

If a symbolic statement appears without parentheses, statements before and after the most dominant connective should be grouped.

The dominance of connectives used in symbolic logic is defined in the following order:

Most dominant:	Biconditional
Same level of dominance:   Conjunction
	Disjunction
	Conditional
Least dominant:	Negation	~
Statement	Most Dominant		Statements Meaning Clarified		Type of
	Connective Highlighted		with Grouping Symbols		Statement
	in Red
p   q   ~r	p   q   ~r		p   (q   ~r)		Conditional
p   q~r	p   q~r		(p   q)~r		Conditional
pqr	pqr		p(qr)		Biconditional
pqr	pqr		(pq)r		Biconditional
p   ~qr   s	p   ~qr   s		(p   ~q)(r   s)		Conditional
p   q   r	p   q   r		The meaning is ambiguous.		?
Ex: Let p, q, and r represent the following simple statements.
p: I fail the course.
q: I study hard.
r: I pass the final.
a.  “I do not fail the course if and only if I study hard and I pass the final”				~p   (q   r )

b.  “I do not fail the course if and only if I study hard, and I pass the final”            (~p        q)       r

Part 3: Truth Tables for Negation, Conjunction, and Disjunction

Negation (not): Opposite truth value from the statement.

p		~p
T		F
F		T

Conjunction (and): Only true when both statements are true.

p	q	p q
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction (or): Only false when both statements are false.

p	q	p q
T	T	T
T	F	T
F	T	T
F	F	F

Ex: Ex: Let p and q represent the following statements: p: 100 > 0

q: -4 < 15

Since both statements are true, then p q is true and p q is true. The statement ~p q will be false because ~p is false.

Ex: Construct a truth table for ~(p     q)

First list the simple statements on top and show all the possible truth values. Second, make a column for p q and fill in the truth values.

Third, construct one more column for ~(p q). The final column tells us that the statement is false only when both p and q are true.

p	q	p   q	~(p   q)
T	T	T	F
T	F	F	T
F	T	F	T
F	F	F	T

A compound statement that is always true is called a tautology. From the table, that means that on its column need to be only Ts, no Fs.

Ex:        p: Brazosport College is a college. (true) q: UHCL is an university. (true)

~(p      q):            “It is not true that BC is a college and UHCL is an university”.

The compound statement ~(p q) is not a tautology because on the last column it contains at least one F.

Ex: A truth table for (~p     q)      ~q:

p   q		~p	~p   q	~q	(~p   q)  ~q
T	T	F	T	F	F
T	F	F	F	T	F
F	T	T	T	F	F
F	F	T	T	T	T

Ex: Construct a truth table for the following statement:

a.  I study hard and ace the final, or I fail the course.

b.  Suppose that you study hard, you do not ace the final and you fail the course. Under these conditions, is this compound statement true or false?

First we represent our statements as follows:

p: I study hard.

q: I ace the final.

r: I fail the course.

Then we write the statement “I study hard and ace the final, or I fail the course” in symbolic form: .

Third, we build the table with three entries (p, q and r):

p	q	r	p  q	(p  q)  r
T	T	T	T	T
T	T	F	T	T
T	F	T	F	T
T	F	F	F	F
F	T	T	F	T
F	T	F	F	F
F	F	T	F	T
F	F	F	F	F

For part b, we have that p is True, q is false and r is true, which means we need to look on the row #3. The conclusion is T, so that, under these conditions, the statement is True.

Not all the time we need to construct the truth table. We can determine the truth value of a compound statement for a specific case in which the truth values of the simple statements are known substituting the truth values of the simple statements into the symbolic form of the compound statement and use the appropriate definitions to determine the truth value of the compound statement.

Ex: On the previous example, part b, we set the truth values: p is True, q is false and r is true. So, the statement has in fact the value .

Part 4: Truth Tables for the Conditional and the Biconditional

	Conditional		pq
p	q		pq
T	T		T
T	F		F
F	T		T
F	F		T

Remark: A conditional is false only when the antecedent is true and the consequent is false.

Ex: A truth table for ~q       ~p:

p	q	~q	~p	~q   ~p
T	T	F	F	T
T	F	T	F	F
F	T	F	T	T
F	F	T	T	T

Ex: A truth table for [( p     q)     ~ p]        q:

p	q	p  q	~p	( p   q)  ~ p	[( p   q)  ~ p]q
T	T	T	F	F	T
T	F	T	F	F	T
F	T	T	T	T	T
F	F	F	T	F	T

Based on the results from the last column, this compound statement is a tautology.

p        q

p if and only if q:			pq and qp
p	q		pq
T	T		T
T	F		F
F	T		F
F	F		T

The Biconditional is True only when the component statements have the same value.

Ex: You receive a letter that states that you have been assigned a Prize Entry Number – 88855566. If your number matches the winning pre-selected number and you return the number before the deadline, you will win $1,000,000.00.

Suppose that your number does not match the winning pre-selected number, you return the number before the deadline and only win a free issue of a magazine. Under these conditions, can you sue the credit card company for making a false claim?

Assign letters to the simple statements in the claim;

p: Your number matches the pre-selected number                       False

q: You return the number before the deadline                               True

r: You win the prize                                                                                     False

Write the underlined claim in the letter in symbolic form: (p q)       r.

Substitute the truth values for p, q, and r to determine the truth value for the letter’s claim: (F T) F, so we have F F which is True.

The truth-value analysis indicates that you cannot sue the credit card company for making a false claim.

Part 5: Equivalent Statements and Variation of Conditional Statements

Equivalent compound statements are made up of the same simple statements and have the same corresponding truth values for all true-false combinations of these simple statements.

If a compound statement is true, then its equivalent statement must also be true. If a compound statement is false, its equivalent statement must also be false.

Using the truth tables, the corresponding columns for the two statements must be identical. The symbol which is used to show an equivalence is .

Ex: Show that p     ~q and ~p       ~q are equivalent.

First we construct a truth table and see if the corresponding truth values are the same:

p	q	~q		p   ~q		~p		~p    ~q
T	T	F		T		F		T
T	F	T		T		F		T
F	T	F		F		T		F
F	F	T		T		T		T

The two shaded columns are identical, so the statements are equivalent. We write this p      ~q    ~p

~q.

Ex: Show that p		q	~q  ~p.
	p	q			p   q		~p	~q		~q    ~p
	T	T			T		F	F		T
	T	F			F		F	T		F
	F	T			T		T	F		T
	F	F			T		T	T		T

The two shaded columns are identical, so the statements are equivalent

The statement ~q ~p is called the contrapositive of the conditional p q. They are logical equivalent.

Ex: Write the equivalent contrapositive for the statement “If you live in Houston, then you live in Texas”.

p: You live in Houston.
q: You live in Texas.
If you live in Houston, then you live in Texas:	p   q.
The contrapositive is in symbolic form:	~q~p,

so that we can write it as an English statement: “If you do not live in Texas, then you do not live in Houston”.

Variations of the Conditional Statement
Name		Symbolic Form		English Translation
Conditional		p	q	If p, then q.
Converse		q	p	If q, then p.
Inverse		~p	~q	If not p, then not q.
Contrapositive		~	~p	If not q, then not p.

Practice Ex: Show that only the contrapositive is logical equivalent with the conditional p    q.

Practice Ex: Show that Converse and Inverse are equivalent.

Ex: The statement “If it’s freezing then is cold” can be written p      q,

where	p:	It’s freezing
	q:	It’s cold.
Converse:		p is “If it’s cold then is freezing”
Inverse:	~p	~q is “If it’s not freezing then is not cold”
Contrapositive: ~		~p is “If it’s not cold then is not freezing”

Part 6: Negations of Conditional Statements and De Morgan’s Laws

Ex: Let’s prove the equivalence: ~(p				q)	p  ~q.
	p	q	p	q		~(p  q)	~q	p  ~q.
	T	T	T			F	F	F
	T	F	F			T	T	T
	F	T	T			F	F	F
	F	F	T			F	T	F

The negation of a conditional statement can be expressed in the following way:

~(p    q)       p  ~q.

Ex: The negation of the statement “If too much homework is given, a class should not be taken”

can be formed using:

p:  Too much homework is given,

q:  A class should be taken.

The symbolic form is p         ~q. The negation of p        ~q is      p      ~(~ q) which simplifies to p       q.

Translating this one into English we have: “Too much homework is given and a class should be taken.”

De Morgan’s Laws:

1.	~(p   q)	~p   ~q;
2.	~(p   q)	~p   ~q;

Ex: The first law is shown in the truth table below.

p	q	p   q		~(p   q)	~p	~q		~p   ~q
T	T	T		F	F	F		F
T	F	F		T	F	T		T
F	T	F		T	T	F		T
F	F	F		T	T	T		T

Practice Ex: Prove the second De Morgan’s Law.

Ex:        a. The statement is given: “All students do homework on weekends and I do not”

The negation is: “Some students do not do homework on weekends or I do”

b. The statement is given: “Some college professors are entertaining lecturers or I’m

bored.”

The negation is: “No college professors are entertaining lecturers and I’m not bored.”

Part 7: Arguments and Truth Tables

An Argument consists of two parts:

Premises: the given statements.

Conclusion: the result determined by the truth of the premises.

If the conclusion is true whenever the premises are assumed to be true then it is a valid argument. An invalid argument is also called a fallacy

Truth tables can be used to test validity:

1.      Use a letter to label each statement in the argument;

2.      Express the premises and the conclusion symbolically;

3.      Construct the truth table and plot the conclusion on the last column;

4.      Check each row were all the premises are True; if all of the corresponding true values on the last column are also Ts, then the argument is valid; otherwise, is invalid.

Ex: If Mr. Teacher is explaining the lesson, then we all pass the Exam. On the next Exam we all passed it.

Building the argument: If Mr. Teacher is explaining the lesson, then we all pass the Exam. On the next Exam we all passed it. Therefore, if Mr. Teacher explains the lesson, we all pass the Exam.

p:  Mr. Teacher is explaining the lesson;

q:  We all pass the exam

We write these symbolically:	p		q	(Premise 1)
		q		(Premise 2)
			p	(Conclusion)

The table is:
		Premise 2		Premise 2	Conclusion
	p	q		p   q	p
	T	T		T	T
	T	F		F	T
	F	T		T	F
	F	F		T	F

The argument is invalid, or a fallacy.

Standard Forms of Arguments

Ex: Determine whether this argument is valid or invalid: “There is no need for makeup because if there is an absence then there is a need for makeup but there is no absence.”

p: There is an absence
q: There is a need for makeup.
Expressed symbolically:
If there is an absence then there is need for makeup			p   q
There is no absence.	.		~p
Therefore, there is no need for makeup.			~q

The argument is in the form of the fallacy of the inverse and is therefore, invalid.

Part 8: Arguments and Euler Diagrams

An Euler diagram is a technique for determining the validity of arguments whose premises contain the words all, some, and no.

Euler Diagrams and Arguments:

1.      Make an Euler diagram for the first premise.

2.      Make an Euler diagram for the second premise on top of the one for the first premise.

3.      The argument is valid if and only if every possible diagram illustrates the conclusion of the argument. If there is even one possible diagram that contradicts the conclusion, this indicates that the conclusion is not true in every case, so the argument is invalid.

Ex:	Premise 1:	All students who arrive late cannot take the test.
	Premise 2:	All students who cannot take the test are ineligible for a passing grade.
	Conclusion:	Therefore, all students who arrive late are ineligible for a passing grade.

		Ineligible for a passing grade
Cannot take test			Cannot take test

Since there is only one possible diagram, and it illustrates the argument’s conclusion the argument is valid.

Ex:	Premise 1:	All cars are expensive.
	Premise 2:	All machines are expensive.
	Conclusion:	Therefore, all cars are machines.

Are expensive

Cars

Adding “All machines are expensive” can be done in four ways:

Are expensive

Are expensive

Are expensive

Are expensive

Machines

Cars

Cars

Cars

Machines

Machines

Cars

Machines

Not all diagrams illustrate the argument’s conclusion that “All cars are machines.” (The first two diagrams do not). The argument is invalid.

Ex:        Premise 1:          All people are mortal.

Premise 2:          Some mortals are cats.

Conclusion:      Therefore, some people are cats.

Cats

The dot in the region of intersection shows that at least one mortal is a cat. The diagram does not show the “people” and “cats” circle intersecting with a dot in the region of intersection.

The argument is valid if and only if every possible diagram illustrates the conclusion of the argument. The argument’s conclusion is: Some people are cats. The diagram does not show the “people” circle and the “cats” circle intersecting with a dot in the region of intersection. The conclusion does not follow from the premises. The argument is invalid.