Logic and Computation in Intelligent Systems, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 6.2 Free with a free account

Logic and Computation in Intelligent Systems

Introduction to Artificial Intelligence · Chapter 6: Logic, Reasoning, and Knowledge SystemsSection 6.2 · lesson 40 of 6915 min · free with a free account

← Analytical Thinking and the Role of Mathematical LogicNext lesson: Building Truth Tables with Propositional Logic →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How Boolean logic, SAT and knowledge bases turn reasoning into computation.

  • Evaluate Boolean expressions and rewrite them with De Morgan's laws
  • Explain satisfiability and why checking every assignment grows as 2 to the n
  • Describe how a knowledge-based agent uses TELL and ASK to answer yes, no or unknown
  • Compare the strengths and limits of symbolic AI

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

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

Opening Question

A Hospital Rule a Machine Can Apply

A hospital has a rule: admit the patient if the fever is high AND the test is positive, OR if a doctor insists. A person can apply that rule, and so can a machine, because it isn't vague. Each part is either true or false, and the parts combine in exact ways. Applying the rule is a form of computation. That idea lies behind one of the oldest approaches to AI: write what an agent knows as logical statements, and let a program work out what follows. How far can that go, and what does it cost?

History

Boole, Shannon and Boolean Operators

In 1854, George Boole showed that reasoning with true and false statements could be written as algebra. In 1937, Claude Shannon showed the same algebra describes electrical switching circuits. That's why a computer's hardware can be built from logic. A Boolean value is true, 1, or false, 0. NOT flips a value. AND is true only when both inputs are true. OR is true when at least one input is true. And XOR, exclusive or, is true when exactly one input is true.

Worked Example

Evaluating an Entry Rule Step by Step

Evaluate a rule step by step. Allow entry equals, has a badge AND NOT on leave, OR is a security guard. Take a person with a badge, who is on leave, and isn't a guard. True AND NOT true, OR false. NOT true is false, so that's true AND false, OR false. True AND false is false. And false OR false is false. Entry denied. A program carries out exactly this kind of evaluation, and the result is always certain.

Equivalence Laws

Double Negation, Distribution and De Morgan

Boolean expressions can be rewritten without changing their meaning, so a program can simplify rules, and check whether two rules are equivalent. Double negation: NOT, NOT A, is just A. Distribution: A AND, B OR C, is the same as, A AND B, OR, A AND C. And De Morgan's laws push a NOT inward. NOT, A AND B, is the same as, NOT A OR NOT B. And NOT, A OR B, is the same as, NOT A AND NOT B. A truth table proves it: try all four combinations of A and B, and both sides always agree.

Circuits

NAND Gates and the Half Adder

Every Boolean function can be built from a single kind of gate. NAND, NOT AND, is false only when both inputs are true, and it can imitate all the others. NOT A is A NAND A. AND is, A NAND B, NANDed with itself. And OR is, A NAND A, NAND, B NAND B. Logic even does arithmetic. A half adder adds two binary digits, with one XOR gate for the sum and one AND gate for the carry. One plus one gives a sum of 0, and a carry of 1. Chains of such adders form a processor's arithmetic unit. And the same operations that switch circuits can test whether a conclusion follows. Reasoning becomes computation.

Quick Check

Test Mode Keeps the Alarm Silent

Quick check. A smoke alarm's rule: sound the alert if, smoke OR heat, AND NOT test mode. Right now there's smoke, no heat, and the system is in test mode. Does the alert sound? Pause, and work it out. It stays silent. Smoke OR heat is true OR false, which is true. NOT test mode is NOT true, which is false. And true AND false is false. It's tempting to stop at smoke, and say it sounds. But the AND needs both sides. And there's no can't tell here: every input is known, so the answer is certain.

Satisfiability

The SAT Problem and Forced Steps

Given an expression with variables, a natural question is: does some assignment of true and false make the whole thing true? That's the satisfiability problem, called SAT. An expression is satisfiable if at least one assignment makes it true. A OR B, AND NOT A, is true when A is false and B is true. It's unsatisfiable if no assignment does, like A AND NOT A. And it's valid, a tautology, if every assignment does, like A OR NOT A. Try one. F is three clauses that must all be true: A OR B; NOT A OR C; and NOT B OR NOT C. Three variables give 2 times 2 times 2, 8 assignments. Checking all eight, two work: A true, B false, C true; and A false, B true, C false. So F is satisfiable. But a search can often skip most of those rows. Guess A is true. The second clause then forces C true. The third clause forces B false. And the first clause is already satisfied. One guess and a few forced steps found a solution. Real solvers propagate consequences like this, and back up when a guess leads to a contradiction.

Exponential Growth

Why Checking Every Assignment Fails

Why not just check everything? With n variables, there are 2 to the n assignments, and every extra variable doubles them. Say a computer checks a billion every second. Twenty variables take about a millisecond. Forty take about 18 minutes. Fifty take 13 days, because ten more variables multiply the time by 1,024. Sixty take about 37 years. And a hundred variables would take about 40 trillion years: far longer than the age of the universe.

Complexity

Cook's Theorem and P Versus NP

SAT has a special feature. Checking a proposed answer is quick: plug in the values, and evaluate. Finding one is the hard part. In 1971, Stephen Cook proved that SAT is NP-complete: among the hardest problems whose answers can be checked quickly. No one has found a method that's fast in the worst case. Whether one exists is the famous open question, P versus NP. Yet the worst case isn't the whole story. Modern SAT solvers, using conflict-driven clause learning, routinely solve formulas with millions of variables, from checking chips and software. Real problems have structure a clever search can exploit.

Decidability

Decidable, Semi-Decidable and Undecidable Questions

A question is decidable if some algorithm always finishes with a correct yes or no, however long it takes. Propositional logic is decidable, since a truth table is finite. Simple if-then rules are fast. Satisfiability is decidable, but exponential in the worst case. Whether a statement follows in first-order logic is only semi-decidable: if it follows, a proof is eventually found. If not, the search may never end. And whether a given program will ever halt is undecidable. Alan Turing proved that in 1936. That same year, Alonzo Church and Turing showed no algorithm can decide every first-order question. And in 1931, Kurt Gödel showed that any consistent system strong enough for arithmetic has true statements it can't prove. The central trade-off: a language that can say more is harder to reason with. So many practical systems deliberately restrict what their rules may express, to buy fast, guaranteed reasoning.

Knowledge-Based Agents

TELL, ASK and the Inference Engine

Now put logic to work. A knowledge-based agent keeps what it knows in a knowledge base: a collection of sentences in a formal language. An inference engine derives new sentences from those it has. The agent uses two operations. TELL adds a sentence to the knowledge base. ASK poses a question, and gets back what the knowledge base implies. It runs a cycle: TELL it the percept, ASK what to do, and TELL it the action taken. This is declarative: you state what's true, and let general-purpose reasoning work out what to do.

Worked Example

A Weather Knowledge Base Conversation

Here's a short conversation with a weather knowledge base. TELL: if it's raining, the grass is wet. TELL: if the sprinkler is on, the grass is wet. TELL: if the grass is wet, the path is slippery. And TELL: it is raining. ASK: is the path slippery? Yes: raining, so wet, so slippery. Nothing said so directly, yet the knowledge base concludes it. ASK: is the sprinkler on? Unknown. TELL: the sprinkler is off. Now ASK again: no. So an ASK has three possible answers: yes, no, or unknown. And unknown isn't a failure. It's an honest report of what is, and isn't, known.

Entailment

True in Every Possible World

What does follows mean, exactly? A knowledge base entails a sentence, if that sentence is true in every possible world, where the knowledge base is true. With four yes-or-no facts, raining, sprinkler, grass wet, and path slippery, there are 2 to the 4th, 16 possible worlds. The first four TELLs rule out all but two. Path slippery is true in both, so it's entailed. Sprinkler on differs between them, so it's unknown. And here's the link to satisfiability: a knowledge base entails a sentence exactly when the knowledge base, plus the opposite of that sentence, can't be satisfied. So every ASK is a SAT question, and its cost matters.

Quick Check

A Barking Dog Leaves the Alarm Unknown

Quick check, with a new knowledge base. TELL: if the alarm sounds, the dog barks. TELL: the dog barks. ASK: did the alarm sound? What does the knowledge base answer? Pause, and decide. Unknown. Two worlds fit the knowledge base: the alarm sounded and the dog barked, or the dog barked for some other reason. The alarm differs between them. Yes would be affirming the consequent: the dog barks, so the alarm sounded. That's an invalid form. And nothing rules the alarm out, so no isn't entailed either.

Comparison

Knowledge Bases Versus Hand-Written Programs

Compare a declarative knowledge base with a hand-written program. The knowledge base stores knowledge as sentences you can read and change. The program buries it inside the code. Adding a fact to a knowledge base is just a TELL, with no code changes. The program must be edited and retested. And a knowledge base can explain an answer by showing its chain of inferences. But reasoning can be slow, where a program is fast, because each case is built in. And a knowledge base can handle combinations nobody listed, while a program handles only the cases its programmer anticipated.

History

The Rise of Symbolic AI

Symbolic AI is the approach in which intelligence comes from manipulating explicit symbols with rules and logic. It dominated the field's first few decades. In 1956, the Dartmouth workshop named the field, and the Logic Theorist proved theorems from a famous mathematics text. In the 1970s, expert systems captured specialists' knowledge as if-then rules: DENDRAL for molecular structures, MYCIN for blood infections. In the 1980s, companies adopted them widely. One configured computer orders for a major manufacturer, and was reported to save millions of dollars a year. And the Cyc project began writing down everyday common sense, by hand. Its strengths: transparent reasoning, exact guarantees, little need for data, and rules that are easy to update and audit.

Limitations

Brittleness, Exceptions and the Knowledge Bottleneck

And its limits. The knowledge bottleneck: experts are slow to interview, and much of their skill is hard to put into words. Brittleness: outside the situations the rules expect, the system fails sharply. Exceptions: almost every rule has them. Uncertainty: real facts are often probable, not certain. The scale of common sense: everyday knowledge is vast and unstated. And computational cost, which can grow exponentially. Exceptions cause real trouble. TELL: all birds fly; penguins are birds; Tweety is a penguin. Later, TELL: penguins don't fly. Now the knowledge base contradicts itself, and in standard logic, a contradictory one can prove anything. Default reasoning, birds fly unless we learn otherwise, needs special, more complex methods.

Current Use

AI Winter and Symbolic Methods Today

By the late 1980s, the cost of building and maintaining huge rule sets, and their brittleness, led to disappointment and funding cuts: an AI winter. Methods that learn from data then took over what rules handled poorly, especially perception and language. But symbolic methods didn't disappear. SAT solvers verify chips and software, planning systems schedule actions, rule engines apply tax and insurance rules, and knowledge graphs store facts for search and assistants. And neurosymbolic AI tries to combine learned pattern recognition with explicit reasoning. Symbolic methods are strong at exact reasoning and guarantees, and learning at perception, language, and messy patterns.

Key Takeaways

Logic Becomes Computation

To sum up. Boolean algebra turns logic into computation, in circuits and in reasoning. Checking every assignment takes 2 to the n steps, impossible for even sixty or so variables, yet clever solvers handle huge real cases. Propositional logic is decidable, first-order logic only semi-decidable. A knowledge-based agent TELLs and ASKs, and an ASK answers yes, no, or unknown. And symbolic AI is transparent and exact, but brittle and costly, so today it works alongside learning.

Think About It

A Lending Policy Meets a New Loan

Something to think about. A bank encodes its lending policy as 5,000 rules in a knowledge base. Then a new type of loan appears, that the rules never anticipated. What will the system do, and how should the bank handle it? Which parts of the policy would you keep as explicit rules, and which might be better learned from past decisions?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 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 All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 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

Introduction to Artificial Intelligence 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 Logic and Computation in Intelligent Systems

What is a knowledge-based agent in AI?
A knowledge-based agent keeps what it knows as sentences in a formal language, called a knowledge base, and uses an inference engine to derive new sentences. It works through two operations: TELL adds a sentence, and ASK poses a question and returns what the knowledge base implies. Each cycle, it tells the knowledge base its percept, asks what to do, then tells it the action taken.
What does it mean for a knowledge base to entail a sentence?
A knowledge base entails a sentence when that sentence is true in every possible world where the knowledge base is true. If the knowledge base says the alarm makes the dog bark, and the dog barks, the alarm stays unknown, because worlds with and without it both fit. A knowledge base entails a sentence exactly when the knowledge base plus the sentence's negation is unsatisfiable.
Why is checking every truth assignment impractical for large formulas?
Checking every assignment is impractical because n variables give 2 to the n assignments, and each added variable doubles the work. At a billion checks per second, 40 variables take about 18 minutes, 60 take about 37 years, and 100 would take about 40 trillion years. Stephen Cook proved in 1971 that SAT is NP-complete, yet modern solvers exploit structure to handle millions of variables.
What were the main limitations of symbolic AI?
Symbolic AI struggled with the knowledge bottleneck, since expert skill is slow to capture and hard to put into words, and with brittleness outside the situations its rules expect. Rules have exceptions, real facts are often uncertain, common sense is vast, and reasoning can cost exponential time. By the late 1980s these problems led to an AI winter, and learning from data took over perception and language.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 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 Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 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 Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 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 3 credits in Introduction to Artificial Intelligence.

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

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →