[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [ MATHS ] / notn_9_Tables
[Contents] [Source Text] || [Notation] || [Copyright] || [Contact] [Search ]
Wed Jul 7 12:46:09 PDT 2010

Contents


    Tabular Notations

      Motivation

      Consider the following list of applications: data bases, accounting spread-sheets, determinants, matrices, tableax in symbolic logic, Decisions tables, Truth tables, n-squared charts, Parnas's Function Tables, Trace Tables, And/Or Tables,....

      Practical people have often found it easier to express complex mathematical expressions by using a two dimensional grid of values or expressions. They can be manipulated as precisely as other formulae but are often quicker to write and easier to read.

      Abstract Syntax

    1. ABSTRACT_TABLE::=following
        We assume that a table is made of textual items:
      1. Text::@Sets=Contents of an item
      2. table_identifier::@finite_sets=some way of distinguishing tables.
      3. Item::=Structure with Text:Text & table:table_identifier & row:row_number & col:col_number.
      4. Entry::=Structure with table:table_identifier & row:row_number & col:col_number.
      5. Rows::Nat,
      6. Cols::Nat.
      7. row_number::=1..Rows.
      8. col_number::=1..Cols.

        Where the table, row and col uniquely determine the text of the Item

      9. Table::@Item(table,row,col)<>->Text. [ Functional Dependancies in math_13_Data_Bases ]

        To be precise the above are partial tables - it is possible for there to be no Text associated with a particular entry in the table. A table is complete if every Entry has a Text (even if empty):

      10. Complete::@Item(table,row,col)->Text.

      Example Boolean Table

      ABSTRACT_TABLE with Text={"T","F","-"} & Complete=true.

      Concrete Syntax

        In Poor Richard's Text Format(PRTF) (also known as MATHS) a table is recorded like this
         		.Table heading
        		.Row item	item	item
        		.Item item	item
        		...
         		.Close.Table
        The items in each column areseparated by either a tab in a line or the keyword .Item at the start of a line. Rows start with the keyword .Row.
      1. table::syntax= EOLN ".Table" head_row #row ".Close.Table",
      2. row::= EOLN ".Row" untagged_row,
      3. head_row::= O(untagged_row).
      4. untagged_row::=untagged_item #item.
      5. item::=EOLN ".Item" untagged_item.
      6. untagged_item::=element #(tab element).

        Example PRTF

         	.Table x<y	x=y	x>y
         	.Row max'=y	max'=x	max'=x
         	.Row min'=x
         	.Item min'=y
         	.Item min'=y
         	.Close.Table
        [ Extended Dynamic And/Or tables ] below

      . . . . . . . . . ( end of section Concrete Syntax) <<Contents | End>>

      Applications

        The following are in a rough order of occurence.

        Spread Sheets

        As invented by accountants, long before the appearance of computers.

        Matrices

        Truth Tables

        Truth tables are very well known to logicians, electronic engineers and computer scientists. They systematically list all possible values of variables, subexpressions, and expressions. The smallest form is to write the values of subexpression in a column underneath the operator of that subexpression. They are a way to verify tautologies with small numbers of propositional variables.

        Here is a compressed form where vaule are put under both variables and operators:
        Table
        (PandQ)<=P
        (111)11
        (001)10
        (100)11
        (000)10

        (Close Table)

        Karnaugh Maps

        A Karnaugh map is a two dimensional truth table. Here is the above formula in a Karnugh map:
        Table
        -Pnot P
        Q11
        not Q11

        (Close Table)
        Karnaugh maps for more than 2 variables are possible but hard to do in simple HTML. Any pointers to pages?

        In theory, the values in a Karnaugh map can be symbols or expressions. The result are the same as [ Function Tables ] below. [click here [socket symbol] if you can fill this hole]

        Decision Tables

        A decision table is actually made up of two different tables that share common collumns. In the top table the conditions are tabulated. In the lower table are the actions.

        There are two forms. The simplest one lists conditions and actions in the first column and truth values (T,F,-) in the top columns, and letters in the lower half:
        Table
        Conditions12
        x<yTF
        Actions
        min:=xA-
        max:=yB-
        max:=x-A
        min:=y-B

        (Close Table)
        Another format labels the rows and columns (Cn for conditions and An for actions):
        Table
        -Rules12
        C1x<yTF
        A1min:=xA-
        A2max:=yB-
        A3max:=x-A
        A4min:=y-B

        (Close Table)
        The letters indicate what actions are obeyed and the order in which the occur (A before B, before C, and so on). There are simple calculations that verify that every possible case is covered somewhere and that no case is covered more than once. It is not difficult to translate [Humby73] these tables directly into a programming language.

        The only problem people have experienced with decision tables is in maintaining them. Editting manual decision tables is not easy.

        Extended Entry Decision Tables

        In an extended entry table, the conditions can be any expression and the T/F/- entries can indicate any value or set of values. tables.

        Relational Data Bases

        A table with a header and a single row is a simple way to display a tuple/object:
        Table
        NameNumber
        Jane Roe123-456-7890

        (Close Table)
      1. (Name=>"Jane Roe", Number=>"123-456-7890")

        A table with headers and many rows is an instance of a data base:
        Table
        NameNumber
        Jane Roe123-456-7890
        John Doe123-456-7809

        (Close Table)
        In MATHS this is a standard way to express a set of tuples.

      2. { (Name=>"Jane Roe", Number=>"123-456-7890"), (Name=>"John Doe", Number=>"123-456-7809")}

        Queries can be expressed by tables with blank entries.

        And/Or Tables

        These come from the application of logic and state machine theory to the specification of part of a traffic control system: TCAS II [LevesonEtal95] The notation was welcomed by the clients and will become part of the specifications.
      3. ex1::=following,
        Table
        Condition12
        height<200FT
        height<100-T
        droppingT-

        (Close Table)

        The above table states the following condition:

      4. (ex): (height<200 and dropping) or (height<200 and height<100)

        The first column contain predicates and the remaining columns contain "T", "F", "-"(don't care). "T" means the predicate is true and "F" means it is false. Each column means the conjunction(and) of the rows. The table is the disjunction(or) of the meanings of the columns.

        And/Or are used to define, describe, and analyse complex conditions. They are said to be palatable to normal people: [HeimdahlLeveson96] and [LevesonEtal99] for evidence.

        All the standard propositions can be expressed using And/Or tables. Further there are simple (if O(2^n)) algorithms that combine them to derive conclusions, prove results, or find counter examples.


        1. P or Q
          Table
          Condition12
          PT-
          Q-T

          (Close Table)
        2. P and Q
          Table
          Condition1
          PT
          QT

          (Close Table)
        3. if P then Q
          Table
          Condition12
          PF-
          Q-T

          (Close Table)
        4. not P
          Table
          Condition1
          PF

          (Close Table)
        5. not(P and Q)
          Table
          Condition12
          PF-
          Q-F

          (Close Table)
        6. not(P or Q)
          Table
          Condition1
          PF
          QF

          (Close Table)
        7. not(if P then Q)
          Table
          Condition1
          PT
          QF

          (Close Table)

        Extended And/Or Tables

        It seems possible to extend And/Or tables so that the entries stand for values other than "True", "False" and "don't care".

        An interesting avenue of research is to interpret these entries as sets of possible values of expressions. The following re-expresses ex1 using symbolic sets as well as conditions. Here the don't care condition "-" indicates the set {T,F}.

      5. ex2::=following,
        Table
        Condition12
        height0..100100..
        droppingT-

        (Close Table)

        Using [ X/Y Tables ] below we can express Fuzzy Logic [ FUZZY ] as well as standard propositional logic.

        Function Tables

          David Lorge Parnas
        • Tabular Representation of Relations
        • CRL Report 260 Telecommunications Research Institute of Ontario(TRIO) McMaster University Hamilton Ontario Canada 1992

        An example would be good, but my notation and HTML do not easily express all the nuances of these tables: [click here [socket symbol] if you can fill this hole]

        Dynamic And/Or tables

        An And/Or table with dynamic predicates for entries but similar semantics. For example:
      6. (x=y and max'=x and min'=y)or(x>y and max'=x and min'=y)

        would be tabulated as follows:
        Table
        x<yTFF
        x=yFTF
        x>yFFT
        max'=yTTF
        max'=xFTT
        min'=xTTF
        min'=yFTT

        (Close Table)
        The prime (') above indicates the next value of the variable.

        Extended Dynamic And/Or tables

        An Extended And/Or table with dynamic predicates for entries with similar semantics. For example:
      7. (x=y and max'=x and min'=y)or(x>y and max'=x and min'=y)

        could be tabulated as follows:
        Table
        (x,y) in<=>
        max'=yxx
        min'=xyy

        (Close Table)

        If we permit expressions as entries we end up with trace tables:
        Table
        x<yx=yx>y
        max'=ymax'=xmax'=x
        min'=xmin'=ymin'=y

        (Close Table)

        Trace Tables

        Source: Zelkowitz Trace.*table

        TEMPO Tables

        A TEMPO table shows different alternate behaviors of a complex process. Each colmun forms a separate path through the process as a sequence of steps from top to bottom. A TEMPO table uses two of the rules that determine the layout of a temporal map or TEMPO chart.

        For example the relation expression:

      8. (x<=y and min:=x and max:=y) or (x=y and min:=y and max:=min) or ( x>y and max:=x and min=y)

        is tabulated like this:
        Table
        x<yx=yx>y
        min:=xmin:=ymax:=x
        max:=ymax:=minmin:=y

        (Close Table)

        X/Y Tables

        An X/Y table is the general form of an And/Or table or TEMPO Table( Union/Product table). Given any algebra with two infix operators X and Y (some example algebras can be found at [ math_41_Two_Operators.html ] and [ math_45_Three_Operators.html ] ) then an X/Y table is a way to write expressions where X is applied first to create terms and then the terms are combined with the Y operator. For example
      9. |-a*x^2 + b*x + c*1 = following,
        Table
        (*)/(+)
        abc
        x^2x1

        (Close Table)

      10. XYTABLE::=following,
        Net
          Given a set of values
        1. V::Set, equiped with two serial operators
        2. X::serial(V),
        3. Y::serial(V), the meaning of an X/Y table with r:rows, and c:cols, and items item(r,c) is
        4. meaning(X/Y, item)::= Y[c:col_number]X[r:col_number](item(r,c)).

          Note. A serial operator (like and, or, +, *, &, |, etc) can be used as a function of a vector as well as an infix operator:

        5. +(1,2,3,4) = 1+2+3+4 for example. For more see
        6. serial::= See http://www.csci.csusb.edu/dick/maths/notn_12_Expressions.html#Serial Operators.

        (End of Net XYTable)

        For example here is a Composition/Union table showing the WWW standard for encoding data:

      11. URL_encoding::=following,
        Table
        (;)/(|)
        letter digit space char~(letter|digit|space)
        Id Id plus "%" hex

        (Close Table)
        However a popular browser implements the following
      12. IE4_encoding::=following,
        Table
        (;)/(|)
        letter digit space plus char~(letter|digit|space|plus)
        Id Id plus Id "%" hex

        (Close Table)
        For more on URL_encoding see [ URL Encoding in comp.html.syntax ]

        X and Y (above) could be the intersection and union operators of standard set theory [ Extended And/Or Tables ] or of Fuzzy Set Theory:

      13. FUZZY::= See http://www.csci.csusb.edu/dick/maths/math_83_Fuzzy_Sets.html.

      . . . . . . . . . ( end of section Applications) <<Contents | End>>

    . . . . . . . . . ( end of section Tabular Notations) <<Contents | End>>

    Notes on MATHS Notation

    Special characters are defined in [ intro_characters.html ] that also outlines the syntax of expressions and a document.

    Proofs follow a natural deduction style that start with assumptions ("Let") and continue to a consequence ("Close Let") and then discard the assumptions and deduce a conclusion. Look here [ Block Structure in logic_25_Proofs ] for more on the structure and rules.

    The notation also allows you to create a new network of variables and constraints. A "Net" has a number of variables (including none) and a number of properties (including none) that connect variables. You can give them a name and then reuse them. The schema, formal system, or an elementary piece of documentation starts with "Net" and finishes "End of Net". For more, see [ notn_13_Docn_Syntax.html ] for these ways of defining and reusing pieces of logic and algebra in your documents. A quick example: a circle might be described by Net{radius:Positive Real, center:Point, area:=π*radius^2, ...}.

    For a complete listing of pages in this part of my site by topic see [ home.html ]

    Notes on the Underlying Logic of MATHS

    The notation used here is a formal language with syntax and a semantics described using traditional formal logic [ logic_0_Intro.html ] plus sets, functions, relations, and other mathematical extensions.

    For a more rigorous description of the standard notations see

  1. STANDARD::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html

    Glossary

  2. above::reason="I'm too lazy to work out which of the above statements I need here", often the last 3 or 4 statements. The previous and previous but one statments are shown as (-1) and (-2).
  3. given::reason="I've been told that...", used to describe a problem.
  4. given::variable="I'll be given a value or object like this...", used to describe a problem.
  5. goal::theorem="The result I'm trying to prove right now".
  6. goal::variable="The value or object I'm trying to find or construct".
  7. let::reason="For the sake of argument let...", introduces a temporary hypothesis that survives until the end of the surrounding "Let...Close.Let" block or Case.
  8. hyp::reason="I assumed this in my last Let/Case/Po/...".
  9. QED::conclusion="Quite Easily Done" or "Quod Erat Demonstrandum", indicates that you have proved what you wanted to prove.
  10. QEF::conclusion="Quite Easily Faked", -- indicate that you have proved that the object you constructed fitted the goal you were given.
  11. RAA::conclusion="Reducto Ad Absurdum". This allows you to discard the last assumption (let) that you introduced.

End