{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "07d20a7f",
   "metadata": {},
   "source": [
    "# Advanced Concepts for Boolean Functions\n",
    "\n",
    "Understanding the structure of a Boolean function is essential for analyzing\n",
    "the behavior of the Boolean networks they define. In this tutorial, we move\n",
    "beyond the basics of `BooleanFunction` and explore three core concepts:\n",
    "\n",
    "- symmetries among inputs\n",
    "- activities of inputs\n",
    "- average sensitivity of a Boolean function\n",
    "\n",
    "These quantities are tied to redundancy, robustness, and dynamical behavior –\n",
    "concepts that will play a central role in later tutorials on canalization and\n",
    "network dynamics.\n",
    "\n",
    "## What you will learn\n",
    "In this tutorial you will learn how to:\n",
    "\n",
    "- identify symmetry groups of Boolean functions,\n",
    "- compute activities and sensitivities,\n",
    "- choose between exact computation and Monte Carlo estimation,\n",
    "- interpret these quantities in terms of robustness and redundancy.\n",
    "\n",
    "## Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a879bb13",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-03-14T21:16:32.661582Z",
     "iopub.status.busy": "2026-03-14T21:16:32.661221Z",
     "iopub.status.idle": "2026-03-14T21:16:33.434260Z",
     "shell.execute_reply": "2026-03-14T21:16:33.433908Z"
    },
    "lines_to_next_cell": 2
   },
   "outputs": [],
   "source": [
    "import boolforge as bf\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e02e299",
   "metadata": {},
   "source": [
    "## Symmetries in Boolean functions\n",
    "\n",
    "In gene regulation, symmetric variables might represent\n",
    "redundant transcription factor binding sites or functionally equivalent \n",
    "repressors. Identifying symmetries can:\n",
    "\n",
    "- Reduce model complexity\n",
    "- Suggest evolutionary mechanisms (gene duplication)\n",
    "- Identify potential drug targets (symmetric inputs may compensate)\n",
    "\n",
    "A symmetry of a Boolean function is a permutation of input variables that does\n",
    "**not** change its output.\n",
    "\n",
    "- Inputs in the same symmetry group can be swapped freely.\n",
    "- Inputs in different groups cannot.\n",
    "\n",
    "The following three Boolean functions exhibit full, partial, and no symmetry."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1342f285",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-03-14T21:16:33.436337Z",
     "iopub.status.busy": "2026-03-14T21:16:33.436128Z",
     "iopub.status.idle": "2026-03-14T21:16:33.439511Z",
     "shell.execute_reply": "2026-03-14T21:16:33.439243Z"
    },
    "lines_to_next_cell": 2
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x0\tx1\tx2\t|\tf\tg\th\n",
      "-------------------------------------------------\n",
      "0\t0\t0\t|\t0\t0\t0\n",
      "0\t0\t1\t|\t1\t0\t0\n",
      "0\t1\t0\t|\t1\t0\t1\n",
      "0\t1\t1\t|\t0\t1\t0\n",
      "1\t0\t0\t|\t1\t1\t1\n",
      "1\t0\t1\t|\t0\t1\t1\n",
      "1\t1\t0\t|\t0\t1\t1\n",
      "1\t1\t1\t|\t1\t1\t1\n",
      "Symmetry groups of f:\n",
      "   ['x0' 'x1' 'x2']\n",
      "\n",
      "Symmetry groups of g:\n",
      "   ['x0']\n",
      "   ['x1' 'x2']\n",
      "\n",
      "Symmetry groups of h:\n",
      "   ['x0']\n",
      "   ['x1']\n",
      "   ['x2']\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Fully symmetric (parity / XOR)\n",
    "f = bf.BooleanFunction(\"(x0 + x1 + x2) % 2\")\n",
    "\n",
    "# Partially symmetric\n",
    "g = bf.BooleanFunction(\"x0 | (x1 & x2)\")\n",
    "\n",
    "# No symmetry\n",
    "h = bf.BooleanFunction(\"x0 | (x1 & ~x2)\")\n",
    "\n",
    "labels = [\"f\", \"g\", \"h\"]\n",
    "bf.display_truth_table(f, g, h, labels=labels)\n",
    "\n",
    "for func, label in zip([f, g, h], labels):\n",
    "    print(f\"Symmetry groups of {label}:\")\n",
    "    for group in func.get_symmetry_groups():\n",
    "        print(\"  \", func.variables[np.array(group)])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e5c0c94",
   "metadata": {
    "lines_to_next_cell": 2
   },
   "source": [
    "**Interpretation**\n",
    "\n",
    "- `f` is fully symmetric: all variables are interchangeable.\n",
    "- `g` has partial symmetry: `x1` and `x2` are equivalent but `x0` is distinct.\n",
    "- `h` has no symmetries: all inputs play unique roles.\n",
    "\n",
    "These patterns foreshadow the concepts of canalization, and specifically\n",
    "canalizing layers, explored in later tutorials."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d48c63ae",
   "metadata": {},
   "source": [
    "## Degenerate functions\n",
    "\n",
    "A function is **degenerate** if one or more inputs do not matter at all. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "2514a0c0",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-03-14T21:16:33.441117Z",
     "iopub.status.busy": "2026-03-14T21:16:33.441007Z",
     "iopub.status.idle": "2026-03-14T21:16:33.825599Z",
     "shell.execute_reply": "2026-03-14T21:16:33.825283Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "f.is_degenerate() False\n",
      "k.is_degenerate() True\n"
     ]
    }
   ],
   "source": [
    "print(\"f.is_degenerate()\", f.is_degenerate())\n",
    "k = bf.BooleanFunction(\"(x AND y) OR x\")\n",
    "print(\"k.is_degenerate()\", k.is_degenerate())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6852c2df",
   "metadata": {},
   "source": [
    "Detecting degeneracy is NP-hard in general.\n",
    "However even at relatively low degree, such functions are extremely rare unless intentionally created.\n",
    "\n",
    "We can also identify the specific variables that cause a function to be degenerate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7b2b9985",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-03-14T21:16:33.827202Z",
     "iopub.status.busy": "2026-03-14T21:16:33.826983Z",
     "iopub.status.idle": "2026-03-14T21:16:33.829120Z",
     "shell.execute_reply": "2026-03-14T21:16:33.828886Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Non-essential variables: ['y']\n"
     ]
    }
   ],
   "source": [
    "nonessential = [\n",
    "    str(v) for v, t in zip(k.variables, k.get_type_of_inputs())\n",
    "    if t == \"non-essential\"\n",
    "]\n",
    "\n",
    "print(\"Non-essential variables:\", nonessential)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46063536",
   "metadata": {},
   "source": [
    "## Activities and sensitivities\n",
    "\n",
    "Activities and sensitivity quantify how much each input affects the output of\n",
    "a Boolean function.\n",
    "\n",
    "### Activity\n",
    "\n",
    "The activity of input $x_i$ is the probability that flipping $x_i$ changes the\n",
    "function’s output:\n",
    "\n",
    "$$\n",
    "a(f,x_i) = \\Pr[f(\\mathbf{x}) \\neq f(\\mathbf{x} \\oplus e_i)],\n",
    "$$\n",
    "where $e_i=(0,\\ldots,0,1,0,\\ldots,0)$ is the ith unit vector.\n",
    "\n",
    "- If $a = 1$: the variable always matters.\n",
    "- If $a = 0$: the variable is irrelevant (degenerate).\n",
    "- In large random Boolean functions, $a \\approx 0.5$ for all variables.\n",
    "\n",
    "### Average sensitivity\n",
    "\n",
    "The *average sensitivity* of a Boolean function describes \n",
    "how sensitive its output is to changes in its inputs, specifically to a random single-bit flip. \n",
    "The (unnormalized) average sensitivity is the sum of all its activities:\n",
    "\n",
    "$$\n",
    "S(f) = \\sum_i a(f,x_i).\n",
    "$$\n",
    "\n",
    "Division by $n$ yields the *normalized average sensitivity* $s(f)$, \n",
    "which can be readily compared between functions of different degree $n$:\n",
    "\n",
    "$$\n",
    "s(f) = \\frac{S(f)}{n}.\n",
    "$$\n",
    "\n",
    "**Interpretation**\n",
    "\n",
    "In Boolean network theory, the mean normalized average sensitivity $s(f)$\n",
    "determines how perturbations tend to propagate through the system.\n",
    "\n",
    "- If $s(f) < 1$, perturbations tend to die out (*ordered regime*).\n",
    "- If $s(f) > 1$, perturbations typically amplify (*chaotic regime*).\n",
    "- The boundary $s(f) = 1$ defines the *critical regime*.\n",
    "\n",
    "The critical regime is believed to characterize many biological \n",
    "networks (see later tutorials). It represents a balance between order and chaos. \n",
    "Operating at this \"edge of chaos\" may optimize information processing and evolvability.\n",
    "\n",
    "### Exact vs Monte Carlo computation\n",
    "\n",
    "- Exact (`exact=True`) computation enumerates all $2^n$ states; feasible for small $n$.\n",
    "- Monte Carlo (`exact=False`, default) simulation approximates using random samples; scalable\n",
    "  to large $n$.\n",
    "\n",
    "Computational cost guide:\n",
    "\n",
    "- Exact methods: $O(2^n)$ time and space, where $n =$ number of inputs.\n",
    "- Monte Carlo: $O(k)$ time, where $k =$ number of samples.\n",
    "\n",
    "Recommendation:\n",
    "\n",
    "- $n \\leq 10$: Use exact methods (fast, deterministic)\n",
    "- $10 < n \\leq 20$: Use exact if possible, Monte Carlo if repeated computation needed\n",
    "- n > 20: Use Monte Carlo (exact is infeasible)\n",
    "\n",
    "### Computing activities and sensitivities\n",
    "\n",
    "To investigate how to compute the activities and the average sensitivity in `BoolForge`, \n",
    "we work with the linear function `f` from above, as well as with the function `g`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "77c215c2",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-03-14T21:16:33.830465Z",
     "iopub.status.busy": "2026-03-14T21:16:33.830366Z",
     "iopub.status.idle": "2026-03-14T21:16:33.832822Z",
     "shell.execute_reply": "2026-03-14T21:16:33.832533Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Activities of f: [1. 1. 1.]\n",
      "Activities of g: [0.75 0.25 0.25]\n",
      "Normalized average sensitivity of f: 1.0\n",
      "Normalized average sensitivity of g: 0.4166666666666667\n"
     ]
    }
   ],
   "source": [
    "exact = True\n",
    "normalized = True\n",
    "\n",
    "print(\"Activities of f:\", f.get_activities(exact=exact))\n",
    "print(\"Activities of g:\", g.get_activities(exact=exact))\n",
    "\n",
    "print(\"Normalized average sensitivity of f:\", f.get_average_sensitivity(exact=exact, \n",
    "                                                                        normalized=normalized))\n",
    "print(\"Normalized average sensitivity of g:\", g.get_average_sensitivity(exact=exact, \n",
    "                                                                        normalized=normalized))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8204229f",
   "metadata": {},
   "source": [
    "**Interpretation**\n",
    "\n",
    "- For `f` (XOR), flipping any input always flips the output, so $s(f) = 1$.\n",
    "- For `g`, $x_0$ influences the output more often than $x_1$ or $x_2$. 75% of $x_0$ flips and 25% of $x_1$ or $x_2$ flips change the output of `g`. Thus, the normalized average sensitivity of `g` is $\\frac 13*75\\% + \\frac 23 25\\% = \\frac{5}{12}$.\n",
    "\n",
    "This unequal influence is a precursor to canalization, \n",
    "a property investigated in depth in the next tutorial.\n",
    "\n",
    "Exact computation is infeasible for large $n$, so Monte Carlo simulation must\n",
    "be used.\n",
    "\n",
    "When generating such a large function randomly (see Tutorial 4), it is not recommended\n",
    " to require that all inputs are essential, as (i) this is almost certainly the case \n",
    "anyways (the probability that an n-input function does not depend on input $x_i$ is given $1/2^{n-1}$), \n",
    "and (ii) checking for input degeneracy is NP-hard (i.e., very computationally expensive). \n",
    "In this specific case, we thus suggest diverging from BoolForge's default and \n",
    "setting `allow_degenerate_functions=True`. \n",
    "You find more on this and the `random_function` method in Tutorial 4. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b92cd89d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-03-14T21:16:33.834072Z",
     "iopub.status.busy": "2026-03-14T21:16:33.833980Z",
     "iopub.status.idle": "2026-03-14T21:16:34.106316Z",
     "shell.execute_reply": "2026-03-14T21:16:34.105981Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mean activity: 0.4993\n",
      "Normalized average sensitivity: 0.5009\n"
     ]
    }
   ],
   "source": [
    "exact = False\n",
    "n = 25\n",
    "\n",
    "h = bf.random_function(n=n, allow_degenerate_functions=True)\n",
    "\n",
    "activities = h.get_activities(exact=exact)\n",
    "print(f\"Mean activity: {np.mean(activities):.4f}\")\n",
    "print(\n",
    "    f\"Normalized average sensitivity: {h.get_average_sensitivity(exact=exact):.4f}\"\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97697b46",
   "metadata": {
    "lines_to_next_cell": 2
   },
   "source": [
    "**Interpretation**\n",
    "\n",
    "Random Boolean functions satisfy:\n",
    "\n",
    "- mean activity $\\approx 0.5$,\n",
    "- normalized average sensitivity $\\approx 0.5$.\n",
    "\n",
    "Thus, the results for `h` align with known theoretical results. \n",
    "More generally, random Boolean function results define the typical behavior\n",
    "against which biological functions can be compared (see Tutorial 5)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "398feb28",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "In this tutorial you learned:\n",
    "\n",
    "- how to compute symmetry groups,\n",
    "- how to test for input degeneracy,\n",
    "- how to compute activities and sensitivities,\n",
    "- how these quantities relate to robustness and structure.\n",
    "\n",
    "These concepts provide essential foundations for understanding \n",
    "\n",
    "- canalization, the core concept of Tutorial 3,\n",
    "- and the robustness of Boolean networks, explored in Tutorial 8.\n"
   ]
  }
 ],
 "metadata": {
  "jupytext": {
   "cell_metadata_filter": "-all",
   "main_language": "python",
   "notebook_metadata_filter": "-all"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}