Logical Connectives: AND, OR, NOT, and More | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 1.4 Free with a free account

Logical Connectives: AND, OR, NOT, and More

Discrete Mathematics · Chapter 1: Logic and Mathematical ProofSection 1.4 · lesson 4 of 8710 min · free with a free account

← Propositions, Truth Values, and Truth TablesNext lesson: Conditional Statements: If-Then, Converse, Inverse, and Contrapositive →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Combining propositions - and the order to evaluate them in.

  • Define negation, conjunction, and inclusive disjunction
  • Define exclusive or, and say where it differs from inclusive or
  • Evaluate compound propositions using precedence
  • Translate everyday rules into connectives without the usual pitfalls

Transcript

Everything said in the video, section by section (1,440 words). Read along, or search it.

Logic and Mathematical Proof

Logical Connectives: AND, OR, NOT, and More

Section one point three introduced propositions, statements that are simply true or false. This section shows how they combine into richer statements. We'll define negation, conjunction, inclusive or, and exclusive or. And we'll see where exclusive or differs from ordinary or. Just as importantly, we'll see what order to evaluate them in when no parentheses are given.

The Opening Problem

2 Systems, One Toolkit

An employee signs in to a company's cloud dashboard from an unfamiliar laptop. The system doesn't ask one yes-or-no question. Is the password correct? Is this device registered to the account? Has the account been flagged for suspicious activity? Only one specific combination of answers produces access granted. A few floors away, a fire-door alarm panel watches two magnetic sensors on the same door. Normally they agree. Both read closed, or both read open while a delivery comes through. The moment they disagree, a technician needs to know, because disagreement usually means a wiring fault, or a door forced only partway. Both systems are built from the same small toolkit, the four connectives in this section.

Definition 1.4.1

Negation Reverses a Proposition

Let p be a proposition. The negation of p, written with the not symbol and read not p, is true exactly when p is false, and false exactly when p is true. Negation is the only connective here that acts on a single proposition. So it's called unary. The others are binary, each combining two propositions into one truth value. Negation adds no new information about the world. It simply reports the opposite truth value. In the sign-in system, let r be the proposition that the account is locked. The system doesn't track account unlocked as a separate condition. It computes not r directly from r. That matters in software design. A rule written as not r always stays consistent with r. Two independently tracked flags, one for locked and one for unlocked, can drift out of sync if only one gets updated. If r is true, because the account was locked after repeated failed attempts, then not r is false. Access fails, whatever the password and device say.

Definitions 1.4.2 and 1.4.3

Conjunction and Inclusive Disjunction

Now the two binary connectives you'll use most. The conjunction of p and q, read p and q, is true exactly when both are true, and false in every other case. Only the first row of its truth table is true. The inclusive disjunction, read p or q, is true when at least one of them is true, including when both are. It's false only when both are false. So three of its four rows are true. Every row except both false. Conjunction extends naturally to three or more propositions. Because and is associative, how you group the terms doesn't change the result.

Worked Evaluations

One False Operand Is Enough

The sign-in rule is really a three-way conjunction. Grant equals p and q and not r, where p is a valid password, q a registered device, and r a locked account. Suppose the password is valid, the device is registered, and the account isn't locked. Then all three terms are true, and access is granted. Now the same employee tries a personal phone that was never registered. q becomes false, and the whole conjunction is false. Access is denied, even though the password was right and the account unlocked. A single false operand is enough. Disjunction needs more care, because everyday English uses or in two senses. A menu offering soup or salad almost always means exactly one. But the or of logic is inclusive. Take a support alert that fires on s or v, where s is a long wait and v is VIP status. It still fires for a VIP who's also waiting too long. And for a VIP within the time limit, false or true is true. So the alert fires on VIP status alone.

Definition 1.4.4

Exclusive Or: Exactly One

The exclusive or of p and q, read p x or q, is true when exactly one of them is true. It's false when they agree, both true or both false. Back to the fire door. Let S one be sensor one reads open, and S two be sensor two reads open. The tamper rule is alert equals S one exclusive or S two. If both sensors read closed, false exclusive or false is false. Correctly, no alarm. If the door is forced on one side only, true exclusive or false is true. Correctly, an alarm. And during a delivery, when both sensors legitimately read open, true exclusive or true is false. Correctly, no alarm, because the sensors agree. Inclusive or and exclusive or agree on every row except one, the row where both operands are true. Built with an ordinary or, the alarm would go off every single time the door was propped open for a delivery.

Figure 1.4.1

The Opening Scenario as Circuits

This figure shows both rules from the opening as logic-gate circuits. Panel A is the sign-in rule. A three-input AND gate takes p and q directly. Its third input first passes through a NOT gate, the triangle with a small output bubble. So the circuit computes with not r, rather than r itself. Panel B is the tamper rule, built from an exclusive or gate. It's drawn like an OR gate, with one extra curved line on its input side. It outputs true only when the two sensors disagree. That's exactly what a plain OR gate couldn't do without a false alarm at every delivery.

Convention 1.4.1

Order of Operations

Without parentheses, a compound statement needs a fixed evaluation order. Here is the convention this course uses. Negation first, applied to the smallest expression right after it. Then conjunction. Then exclusive or. And disjunction last. Two connectives of the same precedence are evaluated left to right. Parentheses always override the order. The conditional and biconditional, coming in section one point five, sit lower still. This ordering is a convention, not a universal law. Exclusive or wasn't part of classical propositional logic, so sources place it at different levels. That's exactly why security policies, contracts, and program code should parenthesize explicitly, whenever a formula could be read two ways.

Worked Evaluation

Evaluating a Compound Proposition

Let's evaluate a compound proposition. E is not p and q, or p exclusive or not q. By the convention, and binds before exclusive or, which binds before or. So E is the quantity not p and q, or-ed with the quantity p exclusive or not q. Take p true and q false. Negation first. Not p is false, and not q is true. Then conjunction. Not p and q is false and false, which is false. Then exclusive or. p exclusive or not q is true and true, which is false, because the operands agree. And disjunction last. E is false or false. So for these values, E is false.

Table 1.4.5

Every Assignment, Step by Step

This table repeats the derivation for all four assignments, so each intermediate step can be checked on its own. Each row fills not p and not q first, then the conjunction, then the exclusive or, and finally combines the last two with or. Reading down the final column, E is true, false, true, true. Because E is true on some rows and false on others, it's neither a tautology, which is always true, nor a contradiction, which is always false. Its truth genuinely depends on the values of p and q.

Table 1.4.6

The 4 Connectives, and How They're Misread

This table compares the four connectives, and the most common way each is misread when translated from English. Negation is true exactly when p is false, and the English not generally matches it closely. Conjunction is true when both operands are true. But a long list of and conditions in prose can hide that every single one must hold. Inclusive or is true when at least one is true. English or is often used exclusively, which masks that inclusive or still holds when both are true. And exclusive or is true when the operands disagree. It's easily confused with inclusive or, since the two differ on exactly one row.

Takeaways

Choosing the Right Connective

To summarize. Negation is unary. It flips one proposition's truth value without adding information. Conjunction is true only when every operand is true, and extends naturally to three or more. Disjunction is inclusive, a meaning that often differs from everyday or. Exclusive or is true exactly when its operands disagree, the right tool for detecting a mismatch. Without parentheses, this course evaluates not, and, exclusive or, and or, in that order. But specifications should still parenthesize explicitly. Here's something to think about. A store gives a welcome discount to a new account or a first purchase. A developer writes it as n exclusive or f. A shopper who opened an account ten days ago and is making a first purchase gets nothing. Was that intended? And which everyday use of or led the developer there?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Logical Connectives: AND, OR, NOT, and More

What is the difference between inclusive or and exclusive or?
Inclusive or, p \lor q, is true when at least one operand is true, including both, while exclusive or, p \oplus q, is true only when exactly one is true. They agree on every row except the one where p and q are both true. There p \lor q is true but p \oplus q is false. Exclusive or is true exactly when the operands disagree.
What order do you evaluate logical connectives in when there are no parentheses?
This course evaluates \lnot first, then \land, then \oplus, and \lor last, with ties going left to right. Parentheses always override this order. Negation applies only to the smallest expression right after it, so \lnot p \land q means (\lnot p) \land q. Sources place \oplus at different levels, so parenthesize whenever a formula could be read two ways.
How do I evaluate \lnot p \land q \lor p \oplus \lnot q when p is true and q is false?
The expression is false for these values. By precedence it reads (\lnot p \land q) \lor (p \oplus \lnot q). Here \lnot p is false and \lnot q is true. Then \lnot p \land q is false, and p \oplus \lnot q is true \oplus true, which is false because the operands agree. Finally, false \lor false is false.
What mistakes do people make when translating English rules into AND, OR, and XOR?
The biggest mistake is treating English "or" as exclusive when logic's \lor is inclusive. A discount for a "new account or first purchase" should be n \lor f. Writing n \oplus f denies the discount to a shopper who satisfies both. Also remember that a long chain of "and" conditions means every one must be true, so a single false operand makes the whole conjunction false.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →