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
  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  ***NEW!
    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

<ASIN:1871962439>

<ASIN:1871962587>

espbook

 

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 )