boolean-algebra

Boolean algebra

What is Boolean algebra?

• Boolean algebra is a mathematical system used to manipulate Boolean values

• Complex expressions can be made simpler using the rules of Boolean algebra

• This is a more powerful simplification method than Karnaugh maps and can simplify expressions that Karnaugh maps cannot

• There are various different rules that you need to learn and that can then be applied to certain expressions to simplify them

• Combining these rules can mean that complex expressions can be reduced to much simpler ones

General rules

• General AND rules

  • X AND 0 = 0

  • X AND 1 = X

  • X AND A = X

  • NOT X AND X = 0

• Note, the value ox X is unknown and it is used as a placeholder

• Therefore X AND 1 = X means that the output will be whatever the value of X is

• General OR rules

  • X OR 0 = X
    X OR 1 = 1
    X OR A = X
    NOT X OR X = 1

Boolean algebra notation

• In Boolean algebra, expressions are written using shorthand notation:

• A line drawn above a variable or expression means that the value is inverted or negated

• It’s the NOT of that value

• When you see multiple horizontal lines, for example:

• It means the whole expression is negated, not just one part

• Always apply De Morgan’s Law starting with the outermost line first

De Morgan’s Law

What is De Morgan’s Law?

• De Morgan’s Laws are used to simplify Boolean expressions involving negation of conjunctions (AND) or disjunctions (OR)

• They are particularly useful for rewriting logic circuits using only NAND or NOR gates

• There are two key rules:

  1. NOT (A AND B) is equivalent to (NOT A) OR (NOT B)

     

  2. NOT (A OR B) is equivalent to (NOT A) AND (NOT B)

     <img alt=”stack A space plus space B with bar on top equals top enclose A space. space top enclose B” data-mathml=”<math ><semantics><mrow><mover><mrow><mi>A</mi><mo>&#160;</mo><mo>+</mo><mo>&#160;</mo><mi>B</mi></mrow><mo>&#175;</mo></mover><mo>=</mo><menclose notation=”top”><mi>A</mi></menclose><mo>&#160;</mo><mo>.</mo><mo>&#160;</mo><menclose notation=”top”><mi>B</mi></menclose></mrow><annotation encoding=”application/vnd.wiris.mtweb-params+json”>{“fontFamily”:”Times New Roman”,”fontSize”:”18″,”autoformat”:true,”toolbar”:”<toolbar ref=’general’><tab ref=’general’><removeItem ref=’setColor’/><removeItem ref=’bold’/><removeItem ref=’italic’/><removeItem ref=’autoItalic’/><removeItem ref=’setUnicode’/><removeItem ref=’mtext’ /><removeItem ref=’rtl’/><removeItem ref=’forceLigature’/><removeItem ref=’setFontFamily’ /><removeItem ref=’setFontSize’/></tab></toolbar>”}</annotation></semantics></math>” height=”28″ role=”math” src=”data:image/svg+xml;charset=utf8,%3Csvg%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20xmlns%3Awrs%3D%22http%3A%2F%2Fwww.wiris.com%2Fxml%2Fmathml-extension%22%20height%3D%2228%22%20width%3D%22110%22%20wrs%3Abaseline%3D%2222%22%3E%3C!–MathML%3A%20%3Cmath%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F1998%2FMath%2FMathML%22%3E%3Cmover%3E%3Cmrow%3E%3Cmi%3EA%3C%2Fmi%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmi%3EB%3C%2Fmi%3E%3C%2Fmrow%3E%3Cmo%3E%26%23xAF%3B%3C%2Fmo%3E%3C%2Fmover%3E%3Cmo%3E%3D%3C%2Fmo%3E%3Cmenclose%20notation%3D%22top%22%3E%3Cmi%3EA%3C%2Fmi%3E%3C%2Fmenclose%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmo%3E.%3C%2Fmo%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmenclose%20notation%3D%22top%22%3E%3Cmi%3EB%3C%2Fmi%3E%3C%2Fmenclose%3E%3C%2Fmath%3E–%3E%3Cdefs%3E%3Cstyle%20type%3D%22text%2Fcss%22%3E%40font-face%7Bfont-family%3A’horizontalbf65417dcecc7f2b0006e’%3Bsrc%3Aurl(data%3Afont%2Ftruetype%3Bcharset%3Dutf-8%3Bbase64%2CAAEAAAAMAIAAAwBAT1MvMlJxIOAAAADMAAAATmNtYXCwg0j%2FAAABHAAAADRjdnQgAAcAAAAAAVAAAAACZ2x5ZuwE1kUAAAFUAAAAO2hlYWQNciGiAAABkAAAADZoaGVhBusXCAAAAcgAAAAkaG10eGjtB6sAAAHsAAAACGxvY2EAAYSYAAAB9AAAAAxtYXhwBLEEbgAAAgAAAAAgbmFtZReja%2F8AAAIgAAAByXBvc3QB9wD6AAAD7AAAACBwcmVwu5WEAAAABAwAAAAHAAACRwGQAAUAAAQABAAAAAAABAAEAAAAAAAAAQEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAgICAAACOv8xEDev96AAAD6ACWAAAAAAACAAEAAQAAABQAAwABAAAAFAAEACAAAAAEAAQAAQAAI6%2F%2F%2FwAAI6%2F%2F%2F9xSAAEAAAAAAAcAAAABAAABVQGrAasAAwAjGAGwBBCwATywARCwAtSwAhCwBTwAsAQQsAHUsAEQsADUMDERFSE1AasBq1ZWAAABAAAAAQAARVMXc18PPPUAAwQA%2F%2F%2F%2F%2F9Wt7tH%2F%2F%2F%2F%2F1a3u0QAAAAADAAMAAAAACgACAAEAAAAAAAEAAAPo%2F2oAABdwAAD%2F%2FwMAAAEAAAAAAAAAAAAAAAAAAAACAyAAAAGrAAAAAAAAAAAAAAAAADsAAQAAAAIADQACAAAAAAACAIAEAAAAAAAEAABfAAAAAAAAABUBAgAAAAAAAAABAB4AAAAAAAAAAAACAA4AHgAAAAAAAAADADwALAAAAAAAAAAEAB4AaAAAAAAAAAAFABYAhgAAAAAAAAAGAA8AnAAAAAAAAAAIABwAqwABAAAAAAABAB4AAAABAAAAAAACAA4AHgABAAAAAAADADwALAABAAAAAAAEAB4AaAABAAAAAAAFABYAhgABAAAAAAAGAA8AnAABAAAAAAAIABwAqwADAAEECQABAB4AAAADAAEECQACAA4AHgADAAEECQADADwALAADAAEECQAEAB4AaAADAAEECQAFABYAhgADAAEECQAGAA8AnAADAAEECQAIABwAqwBIAG8AcgBpAHoAbwBuAHQAYQBsACAARgBvAG4AdABSAGUAZwB1AGwAYQByAE0AYQB0AGgAcwAgAEYAbwByACAATQBvAHIAZQAgAEgAbwByAGkAegBvAG4AdABhAGwAIABGAG8AbgB0AEgAbwByAGkAegBvAG4AdABhAGwAIABGAG8AbgB0AFYAZQByAHMAaQBvAG4AIAAxAC4AMEhvcml6b250YWxfRm9udABNAGEAdABoAHMAIABGAG8AcgAgAE0AbwByAGUAAAAAAwAAAAAAAAH0APoAAAAAAAAAAAAAAAAAAAAAAAAAALkH%2FwACjYUA)format(‘truetype’)%3Bfont-weight%3Anormal%3Bfont-style%3Anormal%3B%7D%40font-face%7Bfont-family%3A’math105e3f444b77fd674ead956ad23’%3Bsrc%3Aurl(data%3Afont%2Ftruetype%3Bcharset%3Dutf-8%3Bbase64%2CAAEAAAAMAIAAAwBAT1MvMi7iBBMAAADMAAAATmNtYXDEvmKUAAABHAAAAERjdnQgDVUNBwAAAWAAAAA6Z2x5ZoPi2VsAAAGcAAABcWhlYWQQC2qxAAADEAAAADZoaGVhCGsXSAAAA0gAAAAkaG10eE2rRkcAAANsAAAAEGxvY2EAHTwYAAADfAAAABRtYXhwBT0FPgAAA5AAAAAgbmFtZaBxlY4AAAOwAAABn3Bvc3QB9wD6AAAFUAAAACBwcmVwa1uragAABXAAAAAUAAADSwGQAAUAAAQABAAAAAAABAAEAAAAAAAAAQEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAgICAAAAAg1UADev96AAAD6ACWAAAAAAACAAEAAQAAABQAAwABAAAAFAAEADAAAAAIAAgAAgAAACsALgA9%2F%2F8AAAArAC4APf%2F%2F%2F9b%2F1P%2FGAAEAAAAAAAAAAAAAAVQDLACAAQAAVgAqAlgCHgEOASwCLABaAYACgACgANQAgAAAAAAAAAArAFUAgACrANUBAAErAAcAAAACAFUAAAMAA6sAAwAHAAAzESERJSERIVUCq%2F2rAgD%2BAAOr%2FFVVAw