Logical Operators

Remember, you’re doing math

Now that we have propositions which are the basic items of true and false, we will now define operators that we can use to create functions that take in one or more propositions, and output some truth value that represents the result of “combining” our propositions in different ways. For those of you familiar with programming (which should be all my students), these operations should seem very familiar.

NOT

The first and most basic of operations in the operation $NOT$. This operation is pretty straightforward to how we use the word in our everyday sentences. If we use $NOT$ to negate a proposition, statement, expression, etc. then we are flipping the truth value. This means that we are turning a true into a false, and false into true. There is a lot of different notation to represent this, but if we have some proposition $P$, then we write the negation as any of the following $$ \bar{P}, \lnot P, not P, !P, \sim P $$

Personally, I prefer the notation $\bar{P}$, which is what we will be using in this website. However, a true first-order logic class would use $\lnot P$.

Definition: The negation of a proposition $P$, notated as $\bar{P}$, is the opposite truth value of $P$. $\bar{P}$ is sometimes called the compliment of $P$.

Finally, we can write out what is called a truth table for our expression. This is just the act of listing out all possible inputs with their associated outputs¹.

Example 1: Let $P=$“NJIT is a university in New Jersey”. Negate $P$

Example 2: Given $P=1$, what is $\bar{\bar{P}}$??

AND

In our previous operation of $NOT$, we saw that there was one input (which is called a unary operation), and now we will explore our first operation that takes in two inputs: $AND$. Just as before, we can first consider what this does when we speak in English. If I was to tell you that I have a cat and I have a dog, you could infer that individually the statements “I have a cat” and “I have a dog” are both true. In essence that is what $AND$ does, it takes in two truth values, and evaluates to true if and only if both inputs are true. If $P,Q$ are propositions, notationally we can see a few ways of writing this $$ P\cdot Q, P\land Q, PQ, P and Q $$ For me I will be sticking with the $P\cdot Q$ as it has a nice bit of analog to multiplication, which makes remembering it easier. However the logical notation is $P\land Q$.

Definition: The $AND$ operation takes in two truth values $P,Q$ and returns true if both $P,Q$ are true, and false in all other cases

The truth table for $AND$ looks as follows, note that now we have two inputs so there are four possible input cases

Example 3: Let $P=$“CS 241 is a CS class” and $Q=$“NJIT is a NY college”. Is $P\cdot Q$ true?

OR

Just like before, this operation that we are creating for ourselves has meaning that we use in our everyday speech. However in this case our speaking phrases may mislead us, as if I was to tell a student “you can take 10 points extra credit on the final, or a HW assignment” one could assume that there is implied “either” in there. Theres no way that I’d provide the option for both, so it is assumed that you can only have one. Rather here we don’t care how many of the options are true in an $OR$ statement, just that at least one of them is True.

For example, when I say “I would be happy with an 10 or 20 extra credit points”, this means that I’d be happy if I got $10$, if I got $20$, and the (unlikely) case in which I got both $10, 20$. This means the logical $OR$ is “inclusive” and some people on the internet like to make a dad joke about it²

Symbolically for two propositions $P,Q$ then we represent $P$ $OR$ $Q$ as $$ P\lor Q, P+Q, P or Q, P||Q $$ and I will use $P+Q$ for this class, again to make things simpler.

Definition: The $OR$ operation takes in two truth values $P,Q$ and returns true at least one of $P,Q$ is true.

The truth table is given as

Example 4: Let $P=$“CS 241 is a CS class” and $Q=$“NJIT is a NY college”. Is $P+Q$ true?

IMPLIES

Unlike the previous operations, this is one that you likely have yet to see before. Linguistically, we take two statements $P,Q$ and return True if the implication “If $P$, then $Q$” is true. This one has a truth table that is a little counterintuitive, so I will first start by showing the truth table, and then explaining from there.

By “If $P$, then $Q$” is true, you might assume this means “If $P$ (is true), then $Q$ (is true)”, but thats not really the case. In fact, we really only say that this implication is False if the implication leads to a contradiction, which is when a true statement leads to a false statement. A good way to think of this is that we will say $P\rightarrow Q = 0$ if the sentence makes someone a “liar”. Heres an example to explain whats going on

I have a friend Lake who was teased for flaking always at plans³ to the point she was called Flakey Lake. Suppose we make plans to go to a park and she tells us “If it’s not raining, then I won’t flake” where in this case $P=$“It was not raining” and $Q=$“I didn’t flake”, with $P,Q$ being past tense so we can say this is some next morning flame session or something. Now consider the following cases and remember that $P\rightarrow Q=0$ if Lake is a liar.

1. If $P$ is true and $Q$ is true, then Lake is not a liar because it means that it did not rain and she didn’t flake, keeping to her word.
2. If $P$ is true and $Q$ is false, then Lake is a liar because even though it didn’t rain she still flaked.
3. If $P$ is false, then regardless of the value of $Q$ Lake is not a liar because he statement only applied to when it wasn’t raining, she did not say what would happen if it was!

Practically, implications are useful because they form the basis of proofs, for reasons we will later get to. However it’s also important to realize that this is just an operator that we defined via a truth table, so we need to be careful to assign meaning to it when sometimes the statement can be nonsense: for example

Example 5: Let $P=$“CS 241 is a CS class” and $Q=$“NJIT is a NJ college”. Is $P\rightarrow Q$ true?

IF AND ONLY IF

The final operator that we are going to discuss is one that we’ve actually used before, but in a way that you probably didn’t realize was a logical operator. Rather you just probably thought I was being overdramatic. The operator if and only if which for propositions $P,Q$ is notated as $$ P\iff Q, P iff Q $$

is defined in terms of other operators. I usually use iff when I’m writing because its so freaking cool holy crap.

Definition: The if and only if operation is defined as $P\iff Q := (P\rightarrow Q)\cdot (Q\rightarrow P)$⁴

We say this is a bidirectional implication because both $P,Q$ imply each other. When we get to proving claims if you see the statement iff then you know that you actually have to prove both directions of the implication.

Note: hopefully this section makes sense I’m hella tired right now and am probably speaking nonsense 😬

Here is the truth table, notice though that this should look familiar …

This is actually the same truth table as $P=Q$ which is true whenever both propositions hold the same truth value! As such we can say that iff is equivalent to saying that the two statements are the same thing.