Skip to main content
10 votes
Accepted

Does Either...Or means Exclusive Or or Inclusive Or?

Don't try to force formal definitions over common english language. "Either… or" means whatever you want it to mean. There is no convention. Just be precise when you want a formal definition....
Nathaniel's user avatar
  • 15.8k
7 votes

I've heard that it isn't possible to encode product types and sum types in a simply typed lambda calculus, but it seems for me that it's false

A phrase like "it is not possible to encode product types in the simply-typed $\lambda$-calculus (without product types)" means: it is not true that for every type $A$ and type $B$, there ...
varkor's user avatar
  • 661
4 votes

Does Either...Or means Exclusive Or or Inclusive Or?

Natural language is indeed ambiguous and depends a lot on semantics and specific context [ref]. In English, Either/Or usually means Exclusive Or because we tend to use in the situation where two ...
tbhaxor's user avatar
  • 208
4 votes

Tseitin formula on 2-connected graph

Clearly, whether a formula is minimally unsatisfiable depends on the exact details of how it is formulated, so let me give a specific definition of Tseitin formulas. Given a graph $G=(V,E)$ and a ...
Emil Jeřábek's user avatar
2 votes
Accepted

Resolution on weakening rule by derived clause

What proof of the completeness of resolution do you know? Chances are it can be easily adapted to this more general setting. Alternatively, you can reduce it to plain completeness. One way is as ...
Emil Jeřábek's user avatar
2 votes

I've heard that it isn't possible to encode product types and sum types in a simply typed lambda calculus, but it seems for me that it's false

You're looking for Church encodings, which are encodings of type constructions and datatypes in the polymorphic $\lambda$-calculus. That is, apart from having function types $\to$ we also need $\...
Andrej Bauer's user avatar
  • 30.9k
2 votes
Accepted

Complexity of a Set of Formulas

Yes. You can build a Boolean circuit $\beta_n$ of size $O(n \lg n)$, that is equivalent to $\alpha_n$. It works by counting the number of "true"s among the inputs, compares it to $n$, and ...
D.W.'s user avatar
  • 162k
1 vote
Accepted

Is there a model for the given logical formula, and if not, why?

Set all variables to false, that way each implication has a false left-hand-side and thus it's satisfied.
Bernardo Subercaseaux's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible