Tagged Questions

33 views

Checking Boolean Algebra work - Simplification

I am currently working on an assignment for a CE class I am taking, and I wanted to know if I have been simplifying these equations correctly. I'm supposed to reduce them to a sum of products. 1) ...
34 views

Transforming Nested Fixed-Point Formulas into Infinitary Logic Formulas with Finitely many Variables

There is a definition (actually a description of how it could be defined) of a fixed-point logic formula. The formula is in inflationary fixed point logic (IFP) in this case but it could also be ...
38 views

Reference for problems without efficient algorithm (in polynomial time)

I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have: -Boolean satisfiability ...
43 views

Logic question- its about propositional logic and it asks for a valuation for statisfiability

I dont understand this question that comes from a past paper, so please any help is appreciated. The part that i dont understand is what does it mean (question 3) that it wants me to consider the ...
27 views

97 views

Decimal expansion in logic Church thesis

How can we show that the function $n \mapsto e_n$, where $e_n$ is the $n$-th digit in the decimal expansion of $e$, is computable? I have some idea in terms of Cantor's diag. argument, but I need to ...
94 views

156 views

How to find an equivalent formula?

I have a formula: $p \wedge \neg q \implies q \vee \neg p$, and i have calculated a truth table as follows: \begin{array}{c} p&q&\text{Formula}\\ \hline 0&0&1\\ 0&1&1\\ ...
166 views

Function problem vs. decision problem

Take the set $FP$ of number-theoretic functions that are computable in polynomial time. Let us restrict to those functions with range in $\{0,1\}$, $FP_{0,1}$. Is there any correspondence with ...
190 views

639 views

What are the theorems of mathematics proved by a computer so far?

By theorems, I mean the ones you can find in an undergraduate course of mathematics, not the ones you can find in a textbook of automated proofs. I mean by "proved by a computer" that an existing ...
223 views

Can Horn's algorithm be generalized for all logic expressions?

The following is an algorithm to find truth assignments for Horn Formulas: Input: A Horn Formula Output: A satisfying assignment, if one exists Set all variables to false While ...