Introduction to Boolean Logic
Written by Mike James   
Tuesday, 11 March 2025
Article Index
Introduction to Boolean Logic
Truth Tables
Binary arithmetic and flip-flops
Binary arithmetic
Flip Flops - Time Enters the Logic
De Morgan's Laws
Logic, Finite State Machines and Computers

Logic, Finite State Machines and Computers

If you take into account the way a Boolean circuit can change with time, then you have to come to the conclusion that you can build any computational machine using just one type of logic gate. Using nothing but a universal gate you can build combinatorial logic and active devices such as flip-flops and hence the components of memory.

You can see that you can build a finite state machine from nothing but universal logic gates. You can even build a Turing machine, as long as you simulate its tape using memory built from universal logic gates. Of course, in practice, the machine’s memory would be finite and bounded and so you have really just another finite state machine.

It is remarkable that something capable of so much complex behavior as a computer can be built from the most basic of components - the universal logic gate.

Summary

  • George Boole invented a system of logic that encapsulated the way true and false changed when combined using AND, OR and NOT.

  • Boolean logic can be represented by listing the results of all inputs in a table or as an equivalent formula.

  • Boolean operators and more generally Boolean functions can be implemented as electronic modules usually called "gates".

  • You can think of the two values, true and false, as any two states. In particular you can think of them as one and zero, i.e. binary.

  • Boolean operators can be used to implement binary arithmetic and other binary functions.

  • Real logic gates need time to change state and this fact can be made use of to implement devices that aren't simply static logic functions.

  • A computer is built using logic gates that change state, usually under the control of a clock pulse.

  • Logic is used in programming but it isn't as easy as at it seems. In particular De Morgan's Laws summarize the relationship between expressions involving AND and OR.

  • A universal gate or operator is one that can be used to implement any Boolean function. There are a number of universal gates and they all involve negation.

  • It is possible to build a complete computer using nothing but multiple universal gates.

Related Articles

Celebrate the 200th Birthday of George Boole With Logic

Dangerous Logic - De Morgan & Programming

CPU

Getting Started With Digital Logic - Logic Gates

Binary Arithmetic

Binary - Negative Numbers

The Greeks, George Boole and Prolog

Claude Shannon - Information Theory And More

Charles Babbage - The First Computer Visionary 

How Memory Works

The Computer 

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

cover600

Contents

    1. What Is Computer Science?
      Part I What Is Computable?
    2. What Is Computation?
    3. The Halting Problem
    4. Finite State Machines
      Extract 1: Finite State Machines
      Extract 2: Turing Thinking ***NEW!
    5. Practical Grammar
    6. Numbers, Infinity and Computation
      Extract 1: Numbers 
      Extract 2: Aleph Zero The First Transfinite
      Extract 3: In Search Of Aleph-One
      Extract 4: Transcendental Numbers
    7. Kolmogorov Complexity and Randomness
      Extract 1:Kolmogorov Complexity 
    8. The Algorithm of Choice
    9. Gödel’s Incompleteness Theorem 
    10. Lambda Calculus
      Part II Bits, Codes and Logic
    11. Information Theory 
    12. Splitting the Bit 
    13. Error Correction 
    14. Boolean Logic 
      Part III Computational Complexity
    15. How Hard Can It Be?
      Extract 1: Where Do The Big Os Come From
    16. Recursion
      Extract 1: What Is Recursion
      Extract 2: Why Recursion
    17. NP Versus P Algorithms
      Extract 1: NP & Co-NP
      Extract 2: NP Complete

pico book

 

Comments




or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.



Last Updated ( Tuesday, 11 March 2025 )