# Tagged Questions

Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

0answers
347 views

### Constructor And\Or-graph on function transition of the alternating automata

In a And\Or-graph induced by the transition function, each node of $G$ corresponds to a state $q$ belonging to a set $Q$ of the state of the Automaton, for $q$ with $\delta(q,a)=q_1*q_2$, the node is ...
0answers
85 views

### (Co)homology of propositional logic

Sorry if this is a rather vague question, but it seemed like something that might be interesting. Let $P$ be a family of propositions, and let $\mathcal L(P)$ be the set of all compound propositions ...
0answers
42 views

0answers
30 views

### “Relative unsatisfiability” of SAT instances

There's a natural way to view any SAT instance as a variety: just replace the Boolean algebra $2$ of truth values with the corresponding Boolean ring $\mathbb{Z}/2\mathbb{Z}$. (See my answer to Is ...
0answers
51 views

### Relations between statements involving universal quantifier, conditional and biconditional

If we consider two predicates: $b(x)$: x is a boy $c(x)$: x is clever Then, there are four statements involving $∀, b(x), c(x), →$ and $↔$ . These are below along with my interpretation of their ...
0answers
68 views

### Is propositional logic enough to study real analysis?

Is it necessary to study relational logic before starting real anylisis(from Bartle and Scherbert) or propositional logic enough? Also for topics like topology and differential geometry is ...
0answers
22 views

### Converting equivalence to CNF

I have the following scenario which I need to represent in CNF: we have $n$ bins, and $A_{ij}$ holds iff balls $i$ and $j$ are in a consecutive pair of bins such that the first bin of the pair is even-...
0answers
29 views

### Show that the truth function $h$ determined by $(A \lor B) \implies \neg C$ generates all truth functions

Show that the truth function $h$ determined by $(A \lor B) \implies \neg C$ generates all truth functions. Could someone explain how I would go about proving this, or how I would start? I am having a ...
0answers
23 views

### Logic behind an IFF statement

If we have an iff statement such as: $A$ iff $B$, to show $A \Rightarrow B$ is it enough to show that not $B \Rightarrow$ not A?
0answers
45 views

### Satisfiability and validity algorithms?

Any tips for how to go about this? "Assume you have an algorithm A available, that when input with a propositional formula F, shows whether F is satisfiable or unsatisfiable. Construct an ...
0answers
46 views

0answers
35 views

### Construct theory with a condition

I would need some help here. I'm preparing for finals from mathematical logic and as I am browsing through some exercises, I often found these types: Let's say we have 2 propositions $\phi$ and $\psi$...
0answers
473 views

### Translation of English statements to logical expression using nested quantifier and predicates.

I have come across few doubts solving Exercise of Propositional logic and predicates. Here are they, Doubt 1 ...
0answers
41 views

### Monotonic operators in classical logic

Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
0answers
34 views

### Can the OR function be linearly separated?

I have two questions regarding linear functions and propositional calculus: 1) How do you decide if, for example, the OR function can be linearly separated? The answer is Yes, however I don't know ...
0answers
142 views

### Dual formula in propositional logic

There's something I don't understand in my course on propositional logic. In the case of x being a variable, the definition of its dual is x* = x. Right. However, further in the course, there's a ...
0answers
38 views

### Validity of Induction Proof - $\{ \land, \top, \bot \}$ is an incomplete set of connectives

I need to verify a proof of the fact that $\{ \land, \top, \bot \}$ is not complete. I consider $\top$ and $\bot$ to be $0$-ary logical connectives that are constantly true or false. That is for ...
0answers
160 views

### Relationship between Propositional and First Order Logic

The language of Propositional Calculus comprises of the logical connectives and sentential symbols $A,B,C$ etc. The sentential letters can have arbitrary semantics and truth values. Two wff $\phi$ ...
0answers
288 views

### Maximally Consistent Set (Proof by Contradiction)

Yesterday, I asked about feedback for a proof of the following theorem For all $\phi$, $\phi \in \Gamma^{*}$ if and only if $\Gamma^{*} \vdash \phi$. My main concern was the first part $(\to)$, which ...
0answers
438 views

### Inverse function in multi-valued logic through the Webb function

Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function. Then ...
0answers
48 views

### Proof of propositional logic theorem using Induction on Formulas

How to prove the following theorem using induction on formulas? Let V and V' be two valuations of L. Let $\alpha$ be a formula such that V(p) = V'(p), for all atomic formula p that is subformula ...
0answers
48 views

### Encoding a graph coloring problem in SAT/CNF for DPLL algorithm

I'm having trouble trying to convert the following problem to SAT for later application to DPLL: Given a connected, undirected graph G, with k colors $\{ c_1 , ..., c_k \}$ and any number of ...