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.

learn more… | top users | synonyms (1)

5
votes
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 ...
4
votes
0answers
79 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 ...
3
votes
0answers
33 views

Strict order on propositions and interpolation

We can define a strict order on the set of propositions in countably many propositional letters in the following way: $$\varphi\sqsubset\psi \iff (\models \varphi\rightarrow\psi)\, \land (\not\models ...
3
votes
0answers
52 views

How many ternary functionally complete connectives are there?

Today I was reading up once more on some of the nice results regarding functional completeness, notably Post's celebrated classification theorem with the 5 classes that need to be avoided. (See this ...
3
votes
0answers
79 views

Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also ...
3
votes
0answers
90 views

Application of the compactness theorem

In my logic book they ask me to prove the following as a consequence of the compactness theorem for propositional logic. Let $S \subseteq N$ be an infinite set. I have to show that there exists an ...
3
votes
0answers
277 views

meaning of ``partial converse''

In the definition of a commutative ring $(R,+,\times)$, one of the postulates given is that of uniqueness, i.e. that $$ a=a', b=b'\implies a+b=a'+b', ab=a' b'.$$ The text states that for the system ...
3
votes
0answers
79 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
2
votes
0answers
51 views

Are these two logical statements equal?

I found this question from a website: "Neither the fox nor the lynx can catch the hare if the hare is alert and quick." Let: P: The fox can catch the hare Q: The lynx can catch ...
2
votes
0answers
26 views

n-formula for k n-evaluations

I am trying to solve the following problem Let $N = \{0, 1, 2, ...\} $ is the set of natural numbers. Propositional variables are $ A_{n}$ for $n \in N $ . An evaluation $v$ is called ...
2
votes
0answers
24 views

Can an equation be shown to be valid through logic over an continuous range?

I may be asking the impossible - but would appreciate it if someone else were to confirm this for me, rather than me just thinking this... I have a black box function, $f(x)$ that I don't know ...
2
votes
0answers
64 views

How can i solved this using fitch notation?

I have a little problem that is proof this following statement using fitch notation, can anyone help me out? :) |= (t → s) ∧ ¬((s → q) → (t → q)) Thanks in advance.
2
votes
0answers
81 views

Does There Exist A Fourth Independent Axiom Here?

I use Polish notation. The implicational calculus of propositions under detachment and uniform substitution has the following axioms as a basis: ...
2
votes
0answers
69 views

Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
2
votes
0answers
103 views

Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism ...
1
vote
0answers
9 views

Propositional calculus axiom the other way around

I have the following axioms of propositional calculus (as well as modus ponens and the deduction theorem if needed): $$1) (a \to (b \to a))$$ $$2) (((a \to (b \to c)) \to ((a \to b) \to (a \to c)))$$ ...
1
vote
0answers
31 views

When does the dual of $s =s$?

When does $s^*=s$? $s^*$ represents the dual of $s$, where $s$ is a compound proposition involving only $T, F, \wedge, \vee, \neg $, and $s^*$ is obtained by interchanging $T$ for $F$, $F$ for $T$, ...
1
vote
0answers
20 views

From Propositional Calculus Proof to Predicate Calculus Proof

PROVE: If {$\Delta_{i}$} are all deductively closed set of formulae, so is $\cap \Delta_i$. Show with predicate Calculus. Definition: {$\Delta_{i}$} a set $\Delta$ of formulae is deductively closed ...
1
vote
0answers
38 views

Is this deduction false?

Is this deduction accurate? I have been trying to find out how we can get ~~B by showing contradiction by asssuming A.
1
vote
0answers
32 views

How many valuation are there for a set of atoms?

I'm studying propositional logic. On my notebook I wrote: Theorem: If v is a function from ATOMS (set of atoms) into $\{0,1\}$ then exists a unique valuation $[[*]]_v$ such that $[[\psi]]_v=v(\psi)$ ...
1
vote
0answers
60 views

how to prove the following formula via natural deductions $a ∧ ¬a \vdash b ∧ ¬b$

Hi I am trying to prove the following formula via natural deduction and this is what I have so far. I am not sure however if this is entirely correct. If I could get some verification and be pointed ...
1
vote
0answers
45 views

Generating all logic propositions

I'm looking for a way of generating all logic propositions (propositional calculus) in an "algorithmic" way. The equivalence is symbolic, so $\neg\neg a \neq a$ and $\neg a \lor b \neq a \implies b$, ...
1
vote
0answers
31 views

Defining the differentiability of a multivariable function (if/then)

I'm trying to understand differentiability for multivariable functions and am thoroughly confused by the introduction (and the direction of implications in a certain definition) I'm given the ...
1
vote
0answers
32 views

How to solve this equation using semantic equivlence

Hi I am trying to workout the solution to this propositional logic formula using the below semantic equivalence formula but I am stuck. Could someone please help me out. These are the rules ...
1
vote
0answers
22 views

Question in regards to representing propositons with P/~P

In a standard Frege-System does it break any rules to have 'P' stand for, say "Smith is not president"? Is it mandatory that such a statement be represented by '~P', or can it indeed be represented ...
1
vote
0answers
38 views

Soundness of propositional logic proof

Let $$\begin{align} A1&=(p\implies (q\implies p)) \\ A2&=(((p\implies (q \implies r)) \implies ((p\implies q)\implies (p\implies r))) \\ A3&=((\neg p \implies \neg q ) \implies ((\neg p ...
1
vote
0answers
27 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 ...
1
vote
0answers
46 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 ...
1
vote
0answers
56 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 ...
1
vote
0answers
21 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 ...
1
vote
0answers
28 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 ...
1
vote
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?
1
vote
0answers
43 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 ...
1
vote
0answers
46 views

how to determine if formula satisfies without creating a truth table

$(p \wedge q \wedge r) \wedge (\neg p \vee r)$ So far, what I have got is that $(p \wedge q \wedge r)$ satisfies because if $p$, $q$ and $r = 1$ then $(p \wedge q \wedge r)$ also $= 1$. For $(\neg p ...
1
vote
0answers
48 views

Does a Length Always Exist such that a Tautology Always Exists Beyond That Length?

Suppose we have some set of fixed connectives such that tautologies exist and we write everything in Polish notation. The length of a WFF consists of the number of symbols that it has. WFFs can get ...
1
vote
0answers
64 views

Proving strong completeness of propositional logic by assuming weak completeness via algebraic methods.

In logic via algebra (page $93$), Halmos tries to prove strong completeness ( if $S\models q$ then $S\vdash q$) assuming weak completeness ( if $q$ is a valid in the Boolean logic $(A,F)$ then $q\in ...
1
vote
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 ...
1
vote
0answers
443 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 ...
1
vote
0answers
40 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!!
1
vote
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 ...
1
vote
0answers
129 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 ...
1
vote
0answers
35 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 ...
1
vote
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$ ...
1
vote
0answers
271 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 ...
1
vote
0answers
429 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 ...
0
votes
0answers
17 views

Mathematical logic: Predicates, formula

I've got universum $A = \{0,1,2\}$ Predicate: $R^{A}=\{\{x,y\} \in A \times A \hspace{2mm} | \hspace{2mm} x \neq y \} $ Terms: $f^A(x) = 1$ $g^A(x,y) = min(x,y)$ Constant $c^A = 2$ Valuation: ...
0
votes
0answers
10 views

DNF using laws on 3 literals and simplifying

Can someone tell me how to turn this into disjunctive normal form please? For Q1, I find it easy to remove implications, double negations and use distributive law. However I am having a hard time ...
0
votes
0answers
27 views

First Order Logic Tableau Multiple Universal Identifiers

I've been looking into tableau lately and I have come across multiple Universal Identifiers which I am not used to. How do I approach these to validate/invalidate with these identifiers and provide an ...
0
votes
0answers
36 views

In classical logic ~~p -> p? Intuitionistic?

Is the following rule applicable in classical propositional logic? $\sim (\sim p)\rightarrow p$ In my textbook, it shows that $p \rightarrow\sim(\sim p)$ holds for intuitionistic logic but I was ...
0
votes
0answers
33 views

Create the following wffs(axiom rules for domain) for the domain of lists over alphabet A

Recall that in the domain of Lists over Alphabets, the function cons(a,x) where a is an element in an alphabet and x is a list, produces a new list with a at the beginning of L. The predicate ...