Abstract Search

Intel SEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

On the Validity of Composite Logical Functions

Booth Id:



Finalist Names:
Santiago, Daniel (School: Centro Residencial de Oportunidades Educativas de Mayagüez)

In classical logic, formulas are constructed using a given alphabet composed of connectives and prime statements. The prime statements are assigned one of two truth values: {t,f} and the connectives are functions: C:{t,f}x{t,f}→{t,f}. The truth output of an assignment to the prime statements within P can then be studied via computation. In this research the validity of formulas given the name P were studied, where P is composed of an alphabet including all the possible connectives of the type described above. Within P each of the connectives is assigned a ranking for division of parenthesis. It was then proven making use of complete mathematical induction on the amount of connectives in P or l(P), that any formula P with the connectives displayed bellow absent has an assignment such that its output is t: For all (a,b) where a,b∈{t,f} i(a,b)→t j(a,b)→f The computation of this satisfiable output for P was then defined using binary trees, where each node on the tree corresponds to a connective within P. Then an algorithm was defined to compute the satisfying assignment for P using information “stored at each node”. The information stored at the first node i is the ordered pairs: (a,b) where a,b∈{t,f} such that i(a,b)→t. This procedure is then continued to the nodes on other levels in the binary tree until the terminating nodes are reached and the stored pairs correspond to the satisfying assignment. Lastly, future projections were made about how the results could possibly be extended too many valued logic.

Awards Won:
National Security Agency Research Directorate : Honorable Mention "Science of Security"