Propositional Logic

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.

Some 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.

Some non-propositions:

1. What time is it?
2. Read this carefully.
3. x + 1 = 2.
4. x + y = z.

DEFINITION 1:

Let p be a proposition. Then ¬p is the negation of p. The truth value of ¬p is T if p is false, and F if p is true.
Example:
If p is "All students will pass discrete mathematics, then ¬p is "Not all students will pass discrete mathematics."

DEFINITION 2:

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.

Example:
If p is "It is raining," and q is "It is sunny," then p ∧ q is "it is raining and sunny."

DEFINITION 3:

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:
If p is "It is raining," and q is "It is sunny," then p ∨ q is "it is raining or sunny."

DEFINITION 4:

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 false otherwise.

Example:
If p is "It is night," and q is "It is day," then p ⨂ q is "it is either night or day."

DEFINITION 5:

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).

Some ways of expressing implication:

• if p, then q
• p is sufficient for q
• q if p
• q when p
• p implies q
• p only if q
• q follows from p

For p ⇒ q:

• Converse: q ⇒ p
• Contrapositive: ¬q ⇒ ¬p
• Inverse: ¬p ⇒ ¬q:

Of the above, only the contrapositive always has the same truth value as the original statement.

DEFINITION 6:

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:
The ponds freeze if and only if the temperature is below 32 F.

1. Which of the following is a proposition?
1. Quit while you are ahead.
2. Go to Paris!
3. Paris is the capital of France.
4. What is the capital of Uruguay?
2. Which of the following is a proposition?
1. 1 + 1 = 2
2. x + 1 = 2
3. x + y = z
4. 7 + x = y
3. The bit value for True is
1. 0
2. arbitrary
3. 1
4. A biconditional in formal logic can be best translated to English by
1. either / or
2. if else
3. if then
4. if and only if
5. The difference between or and xor is that
1. p ⨂ q is false if both p and q are true whereas p ∨ q is true in that case.
2. p ⨂ q is true if both p and q are true whereas p ∨ q is false in that case.
3. there is no difference.
6. Which of the following is not a way to express the conditional statement?
1. if p, then q.
2. q follows from p.
3. p only if q.
4. p is insufficient for q.
7. Which of the following sentences has the logical form (p^q)->r?
1. If the weather is rainy and the roads are slippery then John does not feel like going to school.
2. If hshe gets the 8.00 train or the 9.00 train then maybe she can reach on time.
3. Grass courts or clay courts can be used for tennis.
4. Heavy traffic and rain puts Sheela in a bad mood.