Propositional Logic | Propositions

5 min readJan 29, 2021

My discrete mathematics course and explained through CS concepts, once and for all settling the age-old question “When will I ever need this?”.

Definition 1.1:

A proposition is a declarative statement that is either true or false, but it cannot be both. A proposition is a statement that makes an assertion, and this assertion has a truth value. A proposition is NOT a question, opinion, etc.

1.1.a. Truth Value:

Indicates some relation to truth, e.g. being True or False. Sometimes called a logical value.

1.1.b. Propositional Variables:

Letters (most commonly p and q) are used to denote propositions.

IMPORTANT: Any letter (or symbol) can be used to denote propositions. These letters or symbols are simply conventional names given to any propositional statements, and there is no law stating that they must be used. p and q may be replaced by any letter or symbol in your exercises or exams.

Example 1.2:

The following are all examples of propositions:

San Francisco is a city in California. — True

10 x 5>10 — True

10 x 5 <10— False

Think about this:

Why is “10 x 5" itself not a proposition? Because no truth value is asserted.

Is “9x + 3 = 93” a proposition? If we were to assert a value for x, then the overall expression would have meaning, but the truth value is not defined as long as the value of x is unknown.

Example 1.3:

Let p be the statement “George Washington sneezed an odd amount of times”. There is no way to prove that George Washington sneezed an odd number of times. He certainly must have sneezed. He must have sneezed either an odd number or an even number of times. But there is no way to know for sure.

Does p have a truth value?

Yes. Even though we do not know the truth value of p, it still exists. p is a proposition because it asserts some (unknown) truth value. cool huh?

Definition 1.4:

Let p be a proposition. The negation of p is denoted by ~p. In plain English, ~p means to say “It is not the case that p” or “not p”. The truth value of ~p is the opposite of the truth value of p. For example, if p has the truth value True, then ~p would have the truth value of False.

IMPORTANT: Be careful when negating to ensure the negation has the opposite truth value of the original proposition. For example, let the p be the proposition “My mother was born in Canada”. ~p could not be “My mother was born in Nigeria”. If my mother was actually born in America, then both of these statements are false. The negation must include all possible cases where the original statement could be the opposite truth value. How could we do this? How about “It is not the case that my mother was born in Canada” or “My mother was not born in Canada”.

Problem 1.5:

Negate the following:

Dalmations are dogs.
Cats poop ice cream.
Margaritas are made with limes.
There are 435 members of the U.S. House of Representatives.

One easy way to complete these is to place something like “It is not the case that. . .” in front of each sentence, or adding not after the verbs “are” and “poop”.

Definition 1.7:

Let p and q be propositions, as defined above. The conjunction of p and q, denoted by p ∧ q. This conjunction of p and q is true only when p and q are both true. If EITHER p OR q is false, then the entire conjunction p ∧ q is false. A disjunction is the proposition “p or q” and is denoted as p ∨ q. This disjunction remains true when either p or q is false and is only false when BOTH p and q are false. The disjunction “or” is inclusive or, meaning that both p and q may be true.

For example, imagine you were at a sandwich shop and someone was taking your order. If you were asked if you want mayo or mustard on your sandwich, you could (for some reason) say yes to both. It would then be true that you have mayo or mustard on your sandwich because, in fact, you have both. Both possibilities may be true or maybe only one possibility may be true for the entire statement to be true. If you are asked if you want your sandwich toasted or not, this is an example of exclusive or, because it is not possible for your sandwich both toasted and not toasted (only one may be true, not both).

1.7.a. Order of Operations.

Now that we have a few operations, it might be helpful to start to define an order of operations. This is the order of operations for our current set of operations:

For example, ~p ∨ q means (~p) ∨ q. Not ~ (p ∨ q)

1.7.b. Truth Tables.

Truth tables are a way to display all possible truth values for a given proposition or propositions. The following are the truth tables for the operations covered so far.