Logic and Propositional

INTRODUCTION
Many algorithms and proofs use logical expressions such as:
“IF p THEN q” or “If p1 AND p2, THEN q1 OR q2”

Therefore it is necessary to know the cases in which these expressions are TRUE or FALSE, that is, to
know the “truth value” of such expressions. We also investigate the truth value of quantified statements,
which are statements which use the logical quantifiers “for every” and “there exist.”

PROPOSITIONS AND COMPOUND STATEMENTS

A proposition (or statement) is a declarative statement which is true or false, but not both. Consider, for
example, the following six sentences:
(i) Ice floats in water.
(ii) (ii) China is in Europe.
(iii) 2 + 2 = 4 (v) Where are you going?
(iv) (iv) 2 + 2 = 5 (vi) Do your homework.

→All the following declarative sentences are propositions.

1. Washington, D.C., is the capital of the United States of America.

2. Toronto is the capital of Canada.
3. 1 + 1 = 2.
4. 2 + 2 = 3.

Propositions 1 and 3 are true, whereas 2 and 4 are false.

Some sentences that are not propositions.

Consider the following sentences.

1. What time is it?

2. Read this carefully.
3. x + 1 = 2.
4. x + y = z.

Sentences 1 and 2 are not propositions because they are not declarative sentences.
Sentences 3 and 4 are not propositions because they are neither true nor false.
Note that each of sentences 3 and 4 can be turned into a proposition if we assign values to the
variables

Compound Propositions
Many propositions are composite, that is, composed of subpropositions and various connectives discussed
subsequently. Such composite propositions are called compound propositions.Aproposition is said to be
primitive
if it cannot be broken down into simpler propositions, that is, if it is not composite.
 For example, the above propositions (i) through (iv) are primitive propositions. On the other hand, the
following two propositions are composite:

“Roses are red and violets are blue.” and “John is smart or he studies every night.”

Conjunction, p ∧ q

Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition

“p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise.

Disjunction, p ∨ q

Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition

“p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise.
 EXAMPLE: Students who have taken calculus or computer science can take this class.”
“Students who have taken calculus or computer science, but not both, can enroll in
this class.”

Exclusive OR

Let p and q be propositions. The exclusive or of p and q, denoted by p q, is the proposition

that is true when exactly one of p and q is true and is false otherwise.

Negation, ￢p
Given any proposition p, another proposition, called the negation of p, can be formed by writing “It is not
Let p be a proposition. The negation of p, denoted by￢p (also denoted by p), is the statement “It is not
the case that p.”
The proposition ￢p is read “not p.” The truth value of the negation of p, ￢p, is the opposite of the truth
value of p.
 EXAMPLE:
Find the negation of the proposition
“Michael’s PC runs Linux”
and express this in simple English.
SOLUTION
The negation is
“It is not the case that Michael’s PC runs Linux.”
This negation can be more simply expressed as
“Michael’s PC does not run Linux.”

EXAMPLE
The negation of the proposition
“Vandana’s smartphone has at least 32GB of memory”
and express this in simple English.

SOLUTION
The negation is
“It is not the case that Vandana’s smartphone has at least 32GB of memory.”
This negation can also be expressed as
“Vandana’s smartphone does not have at least 32GB of memory”
or even more simply as
“Vandana’s smartphone has less than 32GB of memory.”

CONDITIONAL STATEMENTS
Let p and q be propositions. The conditional statement p → q is the proposition “if p, then
q.” The conditional statement p → q is false when p is true and q is false, and true otherwise.
In the conditional statement p → q, p is called the hypothesis (or antecedent or premise)
and q is called the conclusion (or consequence).
 Example: Let p be the statement “Maria learns discrete mathematics” and q the
statement “Maria will find a good job.” Express the statement p → q as a
statement in English.

Solution: From the definition of conditional statements, we see that when p is the
statement
“Maria learns discrete mathematics” and q is the statement “Maria will find a
good job,” p → q represents the statement
“If Maria learns discrete mathematics, then she will find a good job.”
There are many other ways to express this conditional statement in English.
Among the most
natural of these are:
“Maria will find a good job when she learns discrete mathematics.”
“For Maria to get a good job, it is sufficient for her to learn discrete
mathematics.”
and
“Maria will find a good job unless she does not learn discrete
mathematics.”

Example : What are the contrapositive, the converse, and the inverse of the
conditional statement
“The home team wins whenever it is raining?”

Solution: Because “q whenever p” is one of the ways to express the conditional

statement
p → q, the original statement can be rewritten as
“If it is raining, then the home team wins.”
Consequently, the contrapositive of this conditional statement is
“If the home team does not 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 does not win.”
Only the contrapositive is equivalent to the original statement.

BICONDITIONAL STATEMENTS
 Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if
and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth
values, and is false otherwise. Biconditional statements are also called bi-implications.

EXAMPLE Let p be the statement “You can take the flight,” and let q be the
statement “You buy a ticket.”
Then p ↔ q is the statement
“You can take the flight if and only if you buy a ticket.”
This statement is true if p and q are either both true or both false, that is, if you
buy a ticket and
can take the flight or if you do not buy a ticket and you cannot take the flight. It
is false when
p and q have opposite truth values, that is, when you do not buy a ticket, but you
can take the
flight (such as when you get a free trip) and when you buy a ticket but you
cannot take the flight
(such as when the airline bumps you).

LOGICAL EQUIVALENCE
The compound propositions p and q are called logically equivalent if p ↔ q is a
tautology.
The notation p ≡ q denotes that p and q are logically equivalent.

EXAMPLE Show that ￢(p ∨ q) and ￢p ∧￢q are logically equivalent.

Solution: The truth tables for these compound propositions are displayed in Table
3. Because
the truth values of the compound propositions ￢(p ∨ q) and ￢p ∧￢q agree for all
possible
combinations of the truth values ofp and q, it follows that￢(p ∨ q) ↔ (￢p ∧￢q) is a
tautology
and that these compound propositions are logically equivalent.
EXAMPLE Show that p → q and ￢p ∨ q are logically equivalent.
Solution:We construct the truth table for these compound propositions in Table 4.
Because the
truth values of ￢p ∨ q and p → q agree, they are logically equivalent.

EXAMPLE Show that p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) are logically equivalent.

This is the distributive
law of disjunction over conjunction.
Solution: We construct the truth table for these compound propositions in Table
5. Because
the truth values of p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) agree, these compound
propositions are
logically equivalent.
TAUTOLOGIES
Some propositions P(p, q, . . .) contain only T in the last column of their truth tables or, in other words, they
are true for any truth values of their variables. Such propositions are called tautologies.

CONTRADICTIONS
a proposition P(p, q, . . .) is called a contradiction if it contains 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 ∨￢p, is a tautology, and the proposition “p and not p,” that is, p∧￢p, is a contradiction.

EXAMPLE :
Let p be the statement “You can take the flight,” and let q be the statement “You buy a ticket.”
Then p ↔ q is the statement

“You can take the flight if and only if you buy a ticket.”
This statement is true if p and q are either both true or both false, that is, if you buy a ticket and
can take the flight or if you do not buy a ticket and you cannot take the flight. It is false when
p and q have opposite truth values, that is, when you do not buy a ticket, but you can take the
flight (such as when you get a free trip) and when you buy a ticket but you cannot take the flight
(such as when the airline bumps you).
ARGUMENTS
An argument is an assertion that a given set of propositions P1, P2, . . . , Pn, called premises, yields (has a
consequence) another proposition Q, called the conclusion. Such an argument is denoted by
P1, P2, . . . , Pn $ Q
The notion of a “logical argument” or “valid argument” is formalized as follows:

Definition: An argument P1, P2, . . . , Pn $ Q is said to be valid if Q is true whenever all the premises
P1, P2, . . . , Pn are true. An argument which is not valid is called fallacy.

Logic Circuits
A logic circuit (or digital circuit) receives input signals p1, p2, . . . , pn, each a
bit [either
0 (off) or 1 (on)], and produces output signals s1, s2, . . . , sn, each a bit. In this
section we will
restrict our attention to logic circuits with a single output signal; in general,
digital circuits may
have multiple outputs.

EXAMPLE Build a digital circuit that produces the output (p ∨￢r) ∧ (￢p ∨ (q ∨￢r))
when given input bits p, q, and r.
EXERCISE WILL BE IN NEXT FILE