Foundations of Boolean Logic | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Foundations of Boolean Logic

Discrete Mathematics · Chapter 13: Boolean Algebra and Logic CircuitsSection 13.1 · lesson 81 of 878 min · free with a free account

← Translation Matrices and Their ApplicationsNext lesson: Boolean Algebra: Laws and Properties →

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

From True and False to 1 and 0: the bridge to circuits.

  • Define Boolean values and variables
  • Compute AND, OR and NOT with truth tables
  • Read the standard gate symbols
  • Match Boolean algebra to propositional logic

Transcript

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

Boolean Algebra and Logic Circuits

Foundations of Boolean Logic

This section opens chapter thirteen, on Boolean algebra and logic circuits. It builds a bridge between the propositional logic of chapter one, and the circuits inside every digital device. We'll meet Boolean values and variables, the three basic operations, and the gate symbols that draw them.

The Opening Problem

Logic, Etched Into Silicon

Chapter one spent real effort on propositions that are strictly true or false, combined with and, or and not, and organized into truth tables. Every digital device performs the identical maneuver, billions of times a second. A phone unlocking its screen. A car's computer deciding whether to trigger an airbag. A thermostat deciding whether to run the furnace. Only the labels change. Not statements, but voltage levels. Not true and false, but one and zero. And not connectives, but gates named AND, OR and NOT, etched directly into silicon. This section is orientation, not proof. The laws for rewriting Boolean expressions come in section thirteen point two. The payoff is practical. A circuit datasheet full of dots, plus signs and prime marks should look like familiar territory, not a whole new subject.

13.1.1

Boolean Values and Variables

A Boolean value is one of two symbols, zero and one. A Boolean variable, like x or y, stands for an unspecified Boolean value. So x is either zero or one. What a value means depends entirely on what it's modeling. In logic, one might mean true. In a circuit, a wire held at high voltage. In a device, on rather than off. In memory, the state of a single stored bit. The algebra doesn't care which interpretation is intended. It only needs exactly two values, combined by fixed rules. That's the same move chapter one made, when it let p stand for any proposition at all.

Table 13.1.1

A Two-Sensor Security Controller

Here's a running example. A home security controller tracks two Boolean variables. x is a door sensor. It's one if the door is open, and zero if it's closed. y is a motion sensor. It's one if motion is detected, and zero otherwise. Each variable independently takes one of two values, so the pair has exactly two times two, or four, combined states. Door closed with no motion. Door closed with motion, perhaps a pet. Door open with no motion. And door open with motion. Nothing here has combined the two variables into a single value yet. That's the job of the operations.

Definition 13.1.2

AND, OR and NOT

Three operations combine Boolean values into new ones. AND, written x dot y, or just x y, equals one exactly when both x and y equal one. OR, written x plus y, equals one exactly when x is one, or y is one, or both. NOT, written x prime, equals one exactly when x is zero, and zero exactly when x is one. It's also called the complement. These three aren't a special case built for one example. Every arithmetic circuit in a processor, every pixel-level decision in a camera sensor, and every rule in a spam filter's binary classifier is, at bottom, some arrangement of AND, OR and NOT gates.

Table 13.1.2

The Three Truth Tables

Here are the complete truth tables for all three, over the four combinations of x and y. Read them against the security controller. X dot y is one only in the last row. The door is open and motion is detected. That's the one combination worth sounding a break-in alarm over. X plus y is one in every row but the first. The door is open, or there's motion, or both. That's a broader condition, good for logging a routine notice. And x prime is one exactly when the door is closed, regardless of y.

Figure 13.1.1

The Standard Gate Symbols

Here are the standard circuit symbols for the three operations, each evaluating the inputs x equals one and y equals zero. The AND gate has a flat back and a rounded front. With inputs one and zero, its output is zero. The OR gate has a curved back and a pointed front. With inputs one and zero, its output is one. The NOT gate is a triangle with a small circle at its output. It takes only x, and turns one into zero. These shapes are what the truth tables look like once they're built from physical switching hardware.

13.1.3

From Boole to Shannon

Boolean algebra is named for George Boole. He introduced this algebra of zeros and ones in his eighteen fifty-four book, An Investigation of the Laws of Thought. His aim was to write ordinary logical reasoning in algebraic form. For over eighty years, it remained a topic in mathematical logic, with no engineering use. That changed in nineteen thirty-eight, when Claude Shannon showed that Boole's algebra describes electrical switching circuits exactly. Every relay or transistor network that only ever fully opens or fully closes a circuit obeys Boolean algebra. That's why it underlies every digital circuit built since. Most programming languages expose the same idea directly. Operators like double ampersand, double bar and exclamation point, or the words and, or, not, perform exactly these three operations.

Table 13.1.3

Same Structure, Two Domains

This table makes the correspondence with chapter one explicit. In propositional logic, the basic object is a proposition. In Boolean algebra, it's a Boolean variable, a circuit or data value. The two possible values are true and false on one side, and one and zero on the other. Conjunction, p and q, becomes x dot y. Disjunction, p or q, becomes x plus y. And negation, not p, becomes x prime. Both are verified the same way, by a truth table. The two frameworks are structurally identical, just applied to different kinds of objects.

Worked Example

One Table, Relabeled

Let p be the proposition, the door is open, and q be, motion is detected. The compound proposition p and q is true exactly when both p and q are true. Its truth table, written with T and F, has exactly the same shape as the x dot y column, written with ones and zeros. Relabel F as zero, T as one, and the and symbol as a dot, and one table turns into the other, row for row. The same relabeling works for OR and for NOT. So every equivalence law proved in chapter one carries straight over. That's exactly why section thirteen point two doesn't need to reprove them from scratch.

Takeaways

Two Values, Three Operations

To summarize. A Boolean variable takes exactly one of two values, zero or one. It's the same two-valued structure as true and false, applied to circuits, switches and data. AND, OR and NOT reproduce the truth-table behavior of and, or and not exactly, when one is read as true and zero as false. The notation resembles arithmetic, but it isn't arithmetic. In Boolean algebra, one plus one is one, not two. And this shared structure, made concrete by Shannon in nineteen thirty-eight, is why circuits of gates can carry out the reasoning chapter one studied in the abstract. Here's something to think about. X dot y agrees with ordinary multiplication on every row. But x plus y gives one plus one equals one. Where exactly does the resemblance to arithmetic break down, and why? And if the notation is that misleading, why might engineers have kept the plus sign for OR anyway?

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 Foundations of Boolean Logic

What is a Boolean variable and what values can it take?
A Boolean variable, such as x or y, stands for an unspecified Boolean value, so it is either 0 or 1. The meaning depends on what is modeled: true or false in logic, high or low voltage in a circuit, or on or off in a device. The algebra only needs two values combined by fixed rules.
How do you compute AND, OR, and NOT with truth tables?
List all four combinations of x and y, then apply each rule. x\cdot y is 1 only when both inputs are 1. x+y is 1 when at least one input is 1. x' flips the input, giving 1 when x=0. For x=1, y=0: x\cdot y=0, x+y=1, x'=0.
How do you recognize the AND, OR, and NOT gate symbols?
Each gate has a distinctive shape. The AND gate has a flat back and a rounded front. The OR gate has a curved back and a pointed front. The NOT gate is a triangle with a small circle at its output and takes one input. With inputs x=1 and y=0, AND outputs 0, OR outputs 1, and NOT turns x into 0.
How does Boolean algebra match propositional logic, and why does 1+1=1?
Boolean algebra has the same structure as propositional logic: true becomes 1, false becomes 0, "and" becomes x\cdot y, "or" becomes x+y, and "not" becomes x'. The plus sign means OR, not addition, so 1+1=1 because OR is 1 when at least one input is 1. It is not ordinary arithmetic.

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 →